-D.Sum of XOR Functions)
思路二进制拆位bit之间互不影响对每一位上的n个数进行线性dplen0[i]以i为最后一个元素的长度是偶数的子区间的总长度eve[i]以i为最后一个元素的长度是偶数的数的个数len0 的增量恰好是eve[i]同理len1的增量恰好是odd[i]不同的是在f为1或者0的时候转移的方式不一样上代码#includebits/stdc.h #define int long long #define fi first #define se second #define endl \n using namespace std; typedef pairint,int pii; const int N1e610; const int mod998244353; vectorintpm; int judge[N],nm[N],inv[N]; int Log2[N]; int kmi(int a,int b){ int res1; while(b){ if(b1) resres*a%mod; aa*a%mod; b1; } return res; } void init(){ nm[0]inv[0]1; for(int i1;i1e6;i){ nm[i]nm[i-1]*i%mod; inv[i]kmi(nm[i],mod-2); } } void euler(int n){ judge[1]1; for(int i2;in;i){ if(!judge[i]){ pm.push_back(i); } for(int j0;pm[j]*in;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 ans0; int n;cinn; vectorinta(n1); for(int i1;in;i) cina[i]; for(int bit0;bit31;bit){ vectorintodd(n10),eve(n10); vectorintlen1(n10),len0(n10); for(int i1;in;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(anslen1[i]*(1LLbit)%mod)%mod; } // if(bit1){ // for(int i1;in;i){ // couteve[i] ; // } // coutendl; // for(int i1;in;i){ // coutodd[i] ; // } // coutendl; // } } coutans; } signed main(){ init(); ios::sync_with_stdio(0);cin.tie(0); // for(int i2;i1e6;i){ // Log2[i]Log2[i/2]1; // } int T1;//cinT; while(T--) solve(); return 0; }
