## Intuition The problem involves computing the sum of bitwise AND operations between two binary numbers, `a` and `b`, as `b` is repeatedly halved (right-shifted). The key insight is to understand how the bitwise AND operation affects the sum and how the binary representation of `b` changes as it is halved. The task is to efficiently compute the sum of these AND operations modulo `998244353`. ## Approach 1. **Reverse the Strings**: Since we will be performing operations from the least significant bit (LSB) to the most significant bit (MSB), it is convenient to reverse the binary strings `a` and `b`. 2. **Precompute Powers of Two**: We need to compute powers of two modulo `998244353` up to the maximum possible length of `b`. This will help in calculating the decimal value of the binary numbers efficiently. 3. **Calculate Prefix Sums for `b`**: Create a prefix sum array for `b` to quickly determine how many `1`s are present from the start up to any given position. This helps in determining the contribution of each bit in `a` to the final sum. 4. **Iterate Over `a`**: For each bit in `a`, if it is `1`, calculate its contribution to the sum. This contribution is determined by the number of `1`s in `b` that align with it when `b` is right-shifted. Use the precomputed powers of two to convert the bit position to its decimal value. 5. **Modulo Operation**: Since the result can be large, take modulo `998244353` at each step to prevent overflow and ensure the result is within bounds. ## Complexity - **Time Complexity**: `O(n + m)`, where `n` is the length of `a` and `m` is the length of `b`. This is due to the need to iterate over both strings and compute prefix sums. - **Space Complexity**: `O(m)`, primarily for storing the prefix sums and powers of two. ## Solution (C++) ```cpp #include using namespace std; const int MOD = 998244353; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; string a, b; cin >> a >> b; reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); vector powerOfTwo(max(n, m) + 1, 1); for (int i = 1; i <= max(n, m); ++i) { powerOfTwo[i] = (powerOfTwo[i - 1] * 2) % MOD; } vector prefixSum(m + 1, 0); for (int i = 0; i < m; ++i) { prefixSum[i + 1] = prefixSum[i] + (b[i] == '1'); } long long result = 0; for (int i = 0; i < n; ++i) { if (a[i] == '1') { if (i < m) { result = (result + powerOfTwo[i] * prefixSum[m - i]) % MOD; } } } cout << result << '\n'; return 0; } ``` This solution efficiently computes the required sum by leveraging prefix sums and modular arithmetic, ensuring it works within the constraints provided by the problem.

Binary Numbers AND Sum

Problem Details