????? 根據(jù)二進制建一棵01字典樹，每個節(jié)點的答案等于左節(jié)點0的個數(shù) * 右節(jié)點1的個數(shù) * 2，遍歷整棵樹就能得到答案。

AC代碼：

#include<cstdio>
using namespace std;
const int mod=998244353;
const int maxn=2;struct node{node *next[maxn]; //0 1節(jié)點 int cnt,level;node(){cnt=0; level=0;next[0]=NULL; next[1]=NULL;}
}*root;long long pp[40];
void deal(){pp[0]=0;pp[1]=1;for(int i=2;i<=30;++i)pp[i]=pp[i-1]*2;
}void Init(){root=new node();
}
void insert_tree(int num){node *p=root,*q;for(int i=1;i<=30;++i){int u=num&pp[i];if(u!=0) u=1;  if(p->next[u]==NULL){q=new node();q->level=i;q->cnt=1;p->next[u]=q;p=p->next[u];}else {p->next[u]->cnt++;p=p->next[u];}}
}long long getAns(node *u){if(u==NULL) return 0;long long ans=0;long long l=0,r=0,lev=0; //特別注意，可能會沒有左右節(jié)點 if(u->next[0]!=NULL) {l=u->next[0]->cnt; lev=u->next[0]->level;}if(u->next[1]!=NULL) {r=u->next[1]->cnt; lev=u->next[1]->level;}ans=(ans+(l * r * pp[lev]) %mod)%mod;for(int i=0;i<2;++i){ans=(ans+getAns(u->next[i])%mod)%mod;}delete u;return ans;
}int main(){deal();int T,n,x,kase=1;scanf("%d",&T);while(T--){Init();scanf("%d",&n);for(int i=0;i<n;++i) {scanf("%d",&x);insert_tree(x);}printf("Case #%d: %lld\n",kase++,getAns(root)*2%mod);}return 0;
}

如有不當之處歡迎指出！

轉(zhuǎn)載于:https://www.cnblogs.com/flyawayl/p/8305483.html

總結(jié)

以上是生活随笔為你收集整理的hdu5296 01字典树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。