HDU--5269 ZYB loves Xor I （字典树）
题目电波： HDU--5269 ZYB loves Xor I
首先我们先解决 ai xor aj 每个数转化为二进制 我们用字典树统计 每个节点 0 和 1 的出现的个数
#include<bits/stdc++.h> using namespace std; #define maxn 50000 #define mod 998244353; struct ac{ int sum,nex[3]; void init(){ sum=0; memset(nex,0,sizeof(nex)); } }tre[maxn*30]; int tot; long long ans=0; void init(){ tot=0;ans=0; memset(tre,0,sizeof(tre)); } void add(int x){ int k=0; for(int j=0;j<=30;j++){ bool fa=(x&(1<<j)); //cout<<fa<<endl; if(tre[k].nex[fa^1]){ int i=tre[k].nex[fa^1]; ans+=1LL*(1LL*1<<j)*tre[i].sum%mod; ans%=mod; } if(tre[k].nex[fa]==0){ tre[k].nex[fa]=++tot; tre[tot].init(); } k=tre[k].nex[fa]; tre[k].sum++; } } int main(){ int t,tt=1; cin>>t; while(t--){ init(); int n; cin>>n; for(int j=0;j<n;j++){ int x; scanf("%d",&x); add(x); } ans*=2; ans%=mod; printf("Case #%d: %lld\n",tt++,ans); } }
三七互娱公司福利 320人发布
查看21道真题和解析