题意
Ran feels boring at home and wants to propose a math problem with Yukari and Chen!
So, here's The Yakumo Family Problem:
Given an integer array a, try to calculate the value of the following equation modulo \(998244353\):
\[\sum_{1\le l_1\le r_1<l_2\le r_2<l_3\le r_3\le n}XOR(l_1, r_1)\times XOR(l_2, r_2)\times XOR(l_3, r_3)
\]
\(XOR(l,r)\) means \(a_l\oplus a_{l+1}\oplus a_{l+2}\dots\oplus a_r\), and \(\oplus\) means bitwise XOR.
\(3\le n\le 2\times 10^5\), \(0\le a_i\le 10^9\)
题解
拆位统计，用前缀和统计方案数。
比较麻烦的点在于两个log不能过，所以方案数必须带上权值。写的时候必须想清楚。
时间复杂度\(O(n\log a)\)
constexpr int N=2e5+10;
int a[N];
int f[N][2], G[N];
int g[N][2][2], H[N][2];
int h[N][2];
int main(){
int n=read<int>();
for(int i=1; i<=n; ++i) read(a[i]);
for(int s=0; s<=29; ++s){
if(a[n]>>s&1){
h[n][0]=0;
h[n][1]=1;
}
else{
h[n][0]=1;
h[n][1]=0;
}
for(int i=n-1; i>=1; --i){
if(a[i]>>s&1){
h[i][0]=h[i+1][1];
h[i][1]=add(1, h[i+1][0]);
}
else{
h[i][0]=add(1, h[i+1][0]);
h[i][1]=h[i+1][1];
}
}
for(int i=n; i>=1; --i){
H[i][0]=add(H[i][0], mul(h[i][0], 1<<s));
H[i][1]=add(H[i][1], mul(h[i][1], 1<<s));
}
}
for(int i=n-1; i>=1; --i){
H[i][0]=add(H[i][0], H[i+1][0]);
H[i][1]=add(H[i][1], H[i+1][1]);
}
for(int s=0; s<=29; ++s){
for(int i=0; i<=1; ++i)for(int j=0; j<=1; ++j) g[n-1][i][j]=0;
g[n-1][a[n-1]>>s&1][0]=H[n][0];
g[n-1][a[n-1]>>s&1][1]=H[n][1];
for(int i=n-2; i>=1; --i){
if(a[i]>>s&1){
g[i][0][0]=g[i+1][1][0];
g[i][0][1]=g[i+1][1][1];
g[i][1][0]=add(H[i+1][0], g[i+1][0][0]);
g[i][1][1]=add(H[i+1][1], g[i+1][0][1]);
}
else{
g[i][0][0]=add(H[i+1][0], g[i+1][0][0]);
g[i][0][1]=add(H[i+1][1], g[i+1][0][1]);
g[i][1][0]=g[i+1][1][0];
g[i][1][1]=g[i+1][1][1];
}
}
for(int i=n-1; i>=1; --i)
G[i]=add(G[i], mul(g[i][1][1], 1<<s));
}
for(int i=n-1; i>=1; --i) G[i]=add(G[i], G[i+1]);
int ans=0;
for(int s=0; s<=29; ++s){
if(a[1]>>s&1){
f[1][0]=0;
f[1][1]=1;
}
else{
f[1][0]=1;
f[1][1]=0;
}
for(int i=2; i<=n; ++i){
if(a[i]>>s&1){
f[i][0]=f[i-1][1];
f[i][1]=add(1, f[i-1][0]);
}
else{
f[i][0]=add(1, f[i-1][0]);
f[i][1]=f[i-1][1];
}
}
for(int i=1; i<=n-2; ++i)
ans=add(ans, mul(mul(f[i][1], 1<<s), G[i+1]));
}
printf("%d\n", ans);
return 0;
}