CF1879D Sum of XOR Functions

记前缀异或和数组 \(s\)，于是题目中的 \(f(l,r)\) 可以被表示成 \(s_r \oplus s_{l-1}\)，转化为求 \(\sum\limits_{l=1}^n \sum \limits_{r=l}^n (s_r \oplus s_{l-1})\times (r-l+1)\)。

再记录 \(4\) 个值，\(cnt_0,cnt_1,sum_0,sum_1\) 分别表示当前已经出现过的 \(0/1\) 的个数，出现的所有 \(0/1\) 的下标和。

从左到右遍历 \(s\) 数组，对于当前遍历到的 \(s_i\)，进行拆位计算贡献。

设 \(s_i\) 的第 \(j\) 位为 \(x\)，那么有 \(cnt_{!x}\) 个数产生贡献，所以原式 \((s_r \oplus s_{l-1})\times (r-l+1)\) 中 \(r\) 的贡献为 \(cnt_{!x} \times i\)，前面的 \(l-1\) 的贡献即为维护的下标和 \(sum_{!x}\)。

参考了 jiangly 的做法，感觉非常优美。

const int N = 3e5 + 5, P = 998244353;
int n, s[N], cnt[2], sum[2];
signed main()
{
    cin >> n;
    R(i, 1, n)
    {
        int x;
        cin >> x;
        s[i] = s[i - 1] ^ x;
    }
    int ans = 0;
    R(j, 0, 31)
    {
        cnt[0] = cnt[1] = sum[0] = sum[1] = 0;
        R(i, 0, n)
        {
            int x = s[i] >> j & 1;
            (ans += ((1ll * i * cnt[!x] % P - sum[!x]) * (1 << j) % P + P) % P) %= P;
            ++cnt[x];
            (sum[x] += i) %= P;
        }
    }
    cout << ans << '\n';
    return 0;
}