[数学杂题 位运算] ZROI 2017 提高6 T1 异或统计

一眼看上去非常难，其实比较套路。对于与位运算有关的问题，可以尝试每位拆开算,我们把 i 与 k 的那项拆开:

∑1≤i<j<k≤n(a[i] xor a[j])∗(a[j] xor a[k])∗(∑t2t[a[i]t≠a[k]t])

=∑t2t∑1≤i<j<k≤n[a[i]t≠a[k]t]∗(a[i] xor a[j])∗(a[j] xor a[k])

怎么算后面那项呢？我们可以枚举中间的 j ，然后发现可以独立算两边：

=∑t2t∑j=2n−1((∑i<j,a[i]t=1a[i] xor a[j])∗(∑j<k,a[k]t=0a[i] xor a[k])+(∑i<j,a[i]t=0a[i] xor a[j])∗(∑j<k,a[k]t=1a[i] xor a[k]))

然后就很简单了，后面 4 个 ∑ 求法类似，都是每位拆开算贡献就好了，对于第 d 位，统计 i=1 到 j−1 中满足 a[i]k=1 的所有数中，第 d 位和 a[j] 不同的个数。很套路。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005,MOD=998244353;
typedef long long LL; 
int n,m,a[maxn],ans,sum[35][2],f1[maxn],f2[maxn];

LL Solve(int pos,int k1,int k2){
memset(f1,0,sizeof(f1)); memset(f2,0,sizeof(f2));
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++){
for(int j=0;j<=30;j++) (f1[i]+=(LL)(1<<j)%MOD*sum[j][((a[i]>>j)&1)^1]%MOD)%=MOD;
if(((a[i]>>pos)&1)==k1) for(int j=0;j<=30;j++) (sum[j][(a[i]>>j)&1]+=1)%=MOD;
    }
memset(sum,0,sizeof(sum));
for(int i=n;i>=1;i--){
for(int j=0;j<=30;j++) (f2[i]+=(LL)(1<<j)%MOD*sum[j][((a[i]>>j)&1)^1]%MOD)%=MOD;
if(((a[i]>>pos)&1)==k2) for(int j=0;j<=30;j++) (sum[j][(a[i]>>j)&1]+=1)%=MOD;
    }
int res=0;
for(int i=1;i<=n;i++) (res+=(LL)f1[i]*f2[i]%MOD)%=MOD;
return res;
}
int main(){
scanf("%d\n",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=0;i<=30;i++) (ans+=(LL)(1<<i)%MOD*((Solve(i,1,0)+Solve(i,0,1))%MOD)%MOD)%=MOD;
printf("%d\n",ans);
return 0;
}