Sum of XOR Functions
题目
有一个序列 \(a\)，计算：
\[\sum\limits_{l=1}^{n}\sum\limits_{r=l}^n(r-l+1)\times \bigoplus\limits_{i=l}^{r}a_i \]思路
位运算的题，我们对于每一位进行考虑，会发现构成了很多个 \(0,1\) 序列，则我们对于每一个序列考虑价值，求和即可。
设 \(b\) 序列为这一位上的 \(0,1\) 序列。
对于 \(0,1\) 序列的一段区间的异或和，只有在这段区间中 \(1\) 的数量为奇数个时才为 \(1\)。
我们用 \(cnt_{i,0/1}\) 表示这一位的零一序列中第 \(i\) 个位置前 \(0/1\) 出现的个数。
用 \(sum_{i,0/1}\) 表示：
\[\sum^{x}_{\{\bigoplus^{i}_{k = x}b_k\} = 0/1}(i - x) \]也就是说，表示对于 \(i\) 位置前所有能满足使 \(\{ \bigoplus^{i}_{k = x} b_k \} = 1\) 的位置 \(x\) 到位置 \(i\) 的距离和。
我们发现当我们预处理完成这些数组时，就可以 \(O(1)\) 求出：\(\sum^{i}_{x = 1} \{\bigoplus^{i}_{k = x} b_k\}\) 的值了。
接下来就是 \(O(n)\) 的复杂度枚举右端点的值即可。
主要思路到此结束。
\(code\)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#define int long long
const int MOD = 998244353;
const int MAXN = 3e5 + 7;
int n,a[MAXN];
int cnt[MAXN][2],sum[MAXN][2];
int pre[MAXN];
int ans = 0;
signed main(){
scanf("%lld", &n);
for(int i = 1;i <= n;i++) scanf("%lld", &a[i]);
for(int w = 0;w <= 31;w++){
memset(cnt,0,sizeof(cnt));
memset(sum,0,sizeof(sum));
memset(pre,0,sizeof(pre));
cnt[0][0] = 1;
for(int i = 1;i <= n;i++){
pre[i] = pre[i - 1];
cnt[i][0] = cnt[i - 1][0];
cnt[i][1] = cnt[i - 1][1];
sum[i][0] = sum[i - 1][0];
sum[i][1] = sum[i - 1][1];
pre[i] += (a[i] >> w) & 1;
if(pre[i] & 1) cnt[i][1]++,sum[i][1] += i;
else cnt[i][0]++,sum[i][0] += i;
}
for(int i = 1;i <= n;i++){
if(pre[i] & 1) ans = (ans + ((cnt[i - 1][0] * i - sum[i - 1][0]) % MOD) * (1 << w) % MOD) % MOD;
else ans = (ans + ((cnt[i - 1][1] * i - sum[i - 1][1]) % MOD) * (1 << w) % MOD) % MOD;
ans = ans % MOD;
}
}
cout<<ans;
return 0;
}