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

时间:2021-04-07 19:16:45

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

1i<j<kn(a[i] xor a[j])(a[j] xor a[k])(t2t[a[i]ta[k]t])

=t2t1i<j<kn[a[i]ta[k]t](a[i] xor a[j])(a[j] xor a[k])

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

=t2tj=2n1((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 j1 中满足 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;
}