Educational Codeforces Round 155 D (CF1879

题目大意

给一个长度为 \(n\) 的数组，求 \(\Sigma_{i=1}^{n} \Sigma_{j=i}^{n} 区间异或和 \times (j-i+1)\)
其中 \(n\leq 3e5,~a[i]\leq 1e9\)

分析

首先注意到由 \(l\) 到 \(r\) 的区间异或和可以转化为 \(sum_{l-1}~XOR~sum_r\)
因此，对于每一个点 \(x\) ，无论它作为上述的 \(sum_{i-1}\) 还是 \(sum_j\) ，如果它的某个二进制位（假设为第 \(k\) 位）为 \(1\) 而另一个值（\(sum_{i-1}\) 或 \(sum_r\) ) 的这一位为 \(0\) ，那么点 \(i\) 的第 \(j\) 位会对整体答案产生 \((1<<j)\times 某个值\) 的贡献

现在考虑这个“某个值”应该怎么算：

对于点 \(x\) 的第 \(k\) 位，这个值是所有第 \(k\) 位为 \(0\) 的点的距离之和

因此设 \(f_{i,j}\) 表示所有第 \(j\) 位为 \(0\) 的点与第 \(i\) 个点的距离之和，考虑从 \(f_{i-1,j}\) 到 \(f_{i,j}\) 的转移：

对于 \(i-1\) 以前的点（包含）：每个点的距离会增加 \(1\)
对于 \(i\) 及以后得点：每个点的距离会减少 \(1\)

那么考虑用一个 \(cnt_{i,j}\) 记录 \(i\) 及以前有多少个点的第 \(j\) 位是 \(0\) （这个很好记录），再记录一下所有数中第 \(j\) 位为 \(0\) 的数有多少个（记为 \(sumbit_j\)）

则 \(f_{i,j}=f_{i-1,j}+cnt_{i-1,j}-(sumbit_j-cnt{i-1,j})\)

计算完 \(f_{i,j}\) 后，如果第 \(i\) 个数的第 \(j\) 位是 \(1\)，答案加上 \((1<<j)\times f_{i,j}\) 即可

Code:

#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
const ll mod = 998244353;
const int N = 3e5 + 5, M = 32;
ll f[N][M], cnt[N][M], a[N], sum[N], ans, sumbit[N];
int n, maxbit;

int main() {
    // freopen("d.txt", "r", stdin);
    IO;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i-1] ^ a[i];
        maxbit = max(maxbit, int(log2(sum[i])));
    }
    maxbit = 30;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= maxbit; j++) {
            if (i != 0) 
                cnt[i][j] = cnt[i-1][j];
            if (!(sum[i] & (1 << j))) {
                sumbit[j]++, cnt[i][j]++;
                f[0][j] = (f[0][j] + i) % mod;
            }   
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= maxbit; j++) {
            f[i][j] = ((f[i-1][j] + 2 * cnt[i-1][j]) % mod - sumbit[j] + mod) % mod;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; (1 << j) <= sum[i]; j++) {
            if (sum[i] & (1 << j)) {
                ans += (1ll << j) * f[i][j];
                ans = (ans % mod + mod) % mod;
            }
        }
    }
    cout << ans;
    return 0;
}