zcmimi's blog
查看原题

点击跳转

我们定义第x个数中从右往左数第i位的贡献:有多少个在x之前的数j满足a_j \bigoplus a_{j+1} \bigoplus ... \bigoplus a_x的第i位是1.

f[x][i]表示第x个数第i位的贡献,a[x][i]表示第x个数第i位是多少。

a[x][i]=0,取j=x不会产生贡献。若j < x,aj \bigoplus a_{j+1} \bigoplus ... \bigoplus a_x=a_j \bigoplus a_{j+1} \bigoplus ... \bigoplus a_{x-1}。所以f[x][i]=f[x-1][i].

a[x][i]=1,取j=x产生1的贡献。若j小于x,aj \bigoplus a_{j+1} \bigoplus ... \bigoplus a_xa_j \bigoplus a_{j+1} \bigoplus ... \bigoplus a_{x-1}相反。所以f[x][i]=(x-1-f[x-1][i])(j小于x的贡献)+1(j=x的贡献)=x-f[x-1][i].

f[x]=f[x][0]×1+f[x][1]×2+f[x][2]×4+...+f[x][31]×2^{31}.

则答案就是f[1]+f[2]+...+f[n].

可以用滚动数组

#include<bits/stdc++.h>
using namespace std;
int n,a,f[32];
long long ans;
int main(){
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        scanf("%d",&a);
        for(j=31;j>-1;--j){
            if(a&(1<<j)) f[j]=i-f[j];
            ans+=1LL*f[j]*(1<<j);
        }
    }
    printf("%lld",ans);
}
LG 3917 异或序列
comment评论
Search
search