Educational Codeforces Round 155 (Rated for Div. 2)-D.Sum of XOR Functions

思路：二进制拆位，bit之间互不影响，对每一位上的n个数进行线性dp

len0[i]以i为最后一个元素的长度是偶数的子区间的总长度

eve[i]以i为最后一个元素的长度是偶数的数的个数

len0 的增量恰好是eve[i]

同理len1的增量恰好是odd[i]

不同的是在f为1或者0的时候转移的方式不一样

上代码：

#include<bits/stdc++.h> #define int long long #define fi first #define se second #define endl '\n' using namespace std; typedef pair<int,int> pii; const int N=1e6+10; const int mod=998244353; vector<int>pm; int judge[N],nm[N],inv[N]; int Log2[N]; int kmi(int a,int b){ int res=1; while(b){ if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res; } void init(){ nm[0]=inv[0]=1; for(int i=1;i<=1e6;i++){ nm[i]=nm[i-1]*i%mod; inv[i]=kmi(nm[i],mod-2); } } void euler(int n){ judge[1]=1; for(int i=2;i<=n;i++){ if(!judge[i]){ pm.push_back(i); } for(int j=0;pm[j]*i<=n;j++){ judge[pm[j]*i]=1; if(i%pm[j]==0) break; } } } int C(int a,int b){ return nm[a]*inv[a-b]%mod*inv[b]%mod; } struct nod{ }; /* len0[i]以i为最后一个元素的长度是偶数的子区间的总长度 eve[i]以i为最后一个元素的长度是偶数的数的个数 len0 的增量恰好是eve[i] 同理len1的增量恰好是odd[i] 不同的是在f为1或者0的时候转移的方式不一样 */ void solve(){ int ans=0; int n;cin>>n; vector<int>a(n+1); for(int i=1;i<=n;i++) cin>>a[i]; for(int bit=0;bit<=31;bit++){ vector<int>odd(n+10),eve(n+10); vector<int>len1(n+10),len0(n+10); for(int i=1;i<=n;i++){ int f=((a[i]>>bit)&1); //odd[i]=odd[i-1],eve[i]=eve[i-1]; if(f){ odd[i]=eve[i-1]+1; eve[i]=odd[i-1]; len1[i]=(len0[i-1]+odd[i])%mod; len0[i]=(len1[i-1]+eve[i])%mod; } else{ eve[i]=eve[i-1]+1; odd[i]=odd[i-1]; len0[i]=(len0[i-1]+eve[i])%mod; len1[i]=(len1[i-1]+odd[i])%mod; } ans=(ans+len1[i]*(1LL<<bit)%mod)%mod; } // if(bit<=1){ // for(int i=1;i<=n;i++){ // cout<<eve[i]<<" "; // } // cout<<endl; // for(int i=1;i<=n;i++){ // cout<<odd[i]<<" "; // } // cout<<endl; // } } cout<<ans; } signed main(){ init(); ios::sync_with_stdio(0);cin.tie(0); // for(int i=2;i<=1e6;i++){ // Log2[i]=Log2[i/2]+1; // } int T=1;//cin>>T; while(T--) solve(); return 0; }