[原创]HDU 5269 ZYB loves Xor I [01字典树]【思维】
2017-01-21 11:15:08 Tabris_ 阅读数:260
博客爬取于2020-06-14 22:42:04
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。https://blog.csdn.net/qq_33184171/article/details/54645157
题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=5269 ----------------------------------------------------------------------------------------. ZYB loves Xor I Accepts: 142 Submissions: 696 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)问题描述 ZYB喜欢研究Xor,现在他得到了一个长度为nn的数组A。于是他想知道:对于所有数对( i , j ) ( i ∈ [ 1 , n ] , j ∈ [ 1 , n ] ) (i,j)(i \in [1,n],j \in [1,n]) ( i , j ) ( i ∈ [ 1 , n ] , j ∈ [ 1 , n ]) ,l o w b i t ( A i x o r A j ) l o w b i t ( A i x o r A j ) lowbit(A_i xor A_j)lowbit(A_ i xor A_ j) l o w bi t ( A i x or A j ) l o w bi t ( A i x or A j ) 之和为多少.由于答案可能过大,你需要输出答案对998244353取模后的值 定义l o w b i t ( x ) = 2 k lowbit(x)=2^ k l o w bi t ( x ) = 2 k ,其中k是最小的满足( x a n d 2 k ) > 0 (x_{} and 2^k) > 0 ( x an d 2 k ) > 0 的数 特别地:lowbit(0)=0
输入描述 一共( T ≤ 10 ) (T \leq10) ( T ≤ 10 ) 组数据,对于每组数据: 第一行一个正整数n,表示数组长度 第二行n个非负整数,第i i i 个整数为A i A_{i} A i n ∈ [ 1 , 5 ∗ 1 0 4 ] , A i ∈ [ 0 , 2 29 ] n \in [1,5*10^4],A_i \in [0,2^{29}] n ∈ [ 1 , 5 ∗ 1 0 4 ] , A i ∈ [ 0 , 2 29 ]
输出描述 每组数据输出一行Case #x: ans。x表示组数编号,从1开始。ans为所求值。
输入样例 2 5 4 0 2 7 0 5 2 6 5 4 0
输出样例 Case #1: 36 Case #2: 40 ----------------------------------------------------------------------------------------. 解题思路:
这道题首先想的是用数组处理二进制每一位的0,1的个数,然后进行统计,在处理一下细节,但是最后发现只有在处理二进制下最后一位为1的数才好统计.于是GG
最后看了题解,提到了字典树,顿时茅塞顿开,
我们只要从低位开始插入字典树中,并统计个数,每次统计就是二进制位上和它相反的数的个数*( 1 < < i ) (1<<i) ( 1 << i ) ,
边插入边统计就好了.
附本题代码 ----------------------------------------------------------------------------------------.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 # include <bits/stdc++.h> using namespace std; # define INF (~(1<<31)) # define INFLL (~(1ll<<63)) # define pb push_back # define mp make_pair # define abs(a) ((a)>0?(a):-(a)) # define lalal puts("*******"); # define s1(x) scanf("%d",&x) # define Rep(a,b,c) for(int a=(b);a<=(c);a++) # define Per(a,b,c) for(int a=(b);a>=(c);a--) # define no puts("NO") typedef long long int LL ; typedef unsigned long long int uLL ; const int MOD = 998244353; const int N = 1500000+5; const double eps = 1e-6; const double PI = acos(-1.0); /***********************************************************************/ int trie[N][2],val[N],cnt; void trieinsert(int x){ int now = 0; for(int i=0;i<30;x>>=1,++i){ if(!trie[now][x%2]) trie[now][x%2]=++cnt; now = trie[now][x%2]; val[now]++; } } LL query(int x){ int now = 0; LL ans =0ll; for(int i=0;i<30;x>>=1,++i){ if(!trie[now][x%2]) trie[now][x%2]=++cnt; ans += (2ll<<i)*val[trie[now][1-x%2]]; ans%=MOD; now = trie[now][x%2]; val[now]++; } return ans ; } int main(){ int _ = 1,kcase ; while(~scanf("%d",&_)){ kcase = 0; while(_--){ int n; scanf("%d",&n); cnt = 0; LL x; LL ans = 0ll; for(int i=0;i<n;i++){ scanf("%I64d",&x); ans+=query(x); ans%=MOD; //printf("%I64d\n",ans); //trieinsert(x); } for(int i=0;i<=cnt;i++){ trie[i][0]=trie[i][1]=val[i]=0; } printf("Case #%d: %I64d\n",++kcase,ans); } } return 0; }