[原创]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])lowbit(AixorAj)lowbit(AixorAj)lowbit(A_i xor A_j)lowbit(A_ i xor A_ j)
之和为多少.由于答案可能过大,你需要输出答案对998244353取模后的值
定义lowbit(x)=2klowbit(x)=2^ k
,其中k是最小的满足(xand2k)>0(x_{} and 2^k) > 0的数
特别地:lowbit(0)=0

输入描述
一共(T10)(T \leq10)组数据,对于每组数据:
第一行一个正整数n,表示数组长度
第二行n个非负整数,第ii个整数为AiA_{i}
n[1,5104],Ai[0,229]n \in [1,5*10^4],A_i \in [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
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;
}