1879D – Sum of XOR Functions

Problem Portal: Problem – 1879D – Codeforces

Binary splitting method handles bit operations

Question: Find $\sum\sum f(l,r) * (r - l + 1) (r >= l, 1 <= l <= n )$ , that is, find the XOR values of all intervals multiplied by their lengths.

Solution:

Because of the derivation of the XOR operation, it was found that the properties of the answer to this formula could not be quickly calculated, and the complexity was O(N * N), so we could only calculate the contribution of each bit to the answer by splitting bits.

First perform the derivation operation on the formula:

$f(l, r) * (r - l + 1) = (r - l + 1) * (2^{j1} + 2^{j2} + 2^{j3} + .. . + 2^{jk}) = 2^{j1} * (r - l + 1) + 2^{j2} * (r - l + 1) + ... + 2^{jk} * (r - l + 1)$

1. Observation: For general intervals $[l, r]$ , and for any binary bit, if the XOR value of this bit in the second system of the interval is 1, it contributes to the answer. Then explore the properties of XOR operation:

Property 1. $1\oplus 1 \oplus 1 \oplus 1 \oplus .... \oplus 1 = cnt[1] \% 2$

Property 2. $0 \oplus 0 \oplus 0 \oplus 0 \oplus ... \oplus 0 = 0$

Property 3. $x \oplus y = y \oplus x$

So only an odd number of 1’s can make this bit contribute to the answer.

2. Now the problem is transformed into finding the total length of all intervals with an odd number of intervals 1 based on the secondary system position x.

The calculation can be O(N) each time, and the time complexity is: $O(N*\log(\max(a[i])))$

At this time, DP needs to be used to process:

Status means:

$cnt[i, 0] :$ Indicates that the number of 1s in the length of the first i is Even prefix interval $[1, i]$ quantity.

$cnt[i, 1] :$ Indicates a prefix interval with an odd number of 1’s in the length of the first i $[1, i]$ quantity.

$sum[i, 0] :$ Indicates a prefix interval with an even number of 1’s in the length of the first i $[1, i]$ .

$sum[i, 1] :$ Indicates a prefix interval with an odd number of 1’s in the length of the first i $[1, i]$ .

For any interval $[l, r]$ The number of 1’s or the parity of the number can be obtained through the prefix parity,

if $[1, r]$ yes If there are odd numbers, then the interval should be passed $[1, l]$ is an even number to get $[l + 1, r]$ is an odd number, if $[1, r]$ is an even number, and can be obtained in the same way.

With this property, how to find $[l + 1, r]$ ? We also think from the perspective of prefix sum, because the following lengths do not match, and their lengths are known to be $sum[i - 1, 1]$ or $sum[i - 1, 0]$ , so you can first regard the interval as having length i, and use $cnt[] * i - sum[]$ , for each paragraph, the total length is subtracted The latter paragraph doesn’t fit, wonderful!

CODE:

#include <bits/stdc + + .h>
#define int long long
#define pb push_back
#define ll long long
using namespace std;
const int N = 3e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;
int n, m;
int a[N], b[N];

signed main() {
    cin >> n;
    for(int i = 1; i <= n; i + + )
        cin >> a[i];
        
    int ans = 0;
    for(int i = 0; i <= 30; i + + ) {
        int x = 0, res = 0;
        for(int j = 1; j <= n; j + + ) {
            b[j] = (a[j] >> i) & amp; 1;
        }
        int sum[2] {0, 0};
        int cnt[2] {1, 0}; // cnt[] means: there are several sequences of even numbers of 1 in front.
        
        for(int j = 1; j <= n; j + + ) {
            x = (x + b[j]) % 2;
            res = (res + cnt[1 - x] * j - sum[1 - x]) % mod;
            cnt[x] = (cnt[x] + 1) % mod, sum[x] = (sum[x] + j) % mod;
        }
        ans = (ans + res * (1ll << i)) % mod;
    }
    
    cout << ans << endl;
    
    return 0;
}