hdu 5269 trie树

现场想到了lowbit(X xor Y)=X和Y从右向左数，对应相同的数的个数+1。。。然而并没有想到接下来用trie树

然后就想排个序试试。。。然后就整个人都不好了啊摔

sol：用trie，一边insert一边输出答案

找出Ai的二进制数翻转后在字母树上的路径，对于路径上每个点x，设他走的边是v，且当前为第k位，则和他xor后lowbit为2k的数的个数为trans(x,v^1)的子树大小。

注意这里v=0or1，即可以取的字符。

仿照lrj的模板写了一次。。结果写残了233。因为没有考虑好0这种情况

lrj模板里插入的都是字符串，不会存在0（也就是空）的情况。然而要想插入数字0就完蛋了

 1     int Insert(LL X)
 2     {
 3         int u=0,dep=1;
 4         while(X!=0)
 5         {
 6             int c=(X&1)+1;
 7             X=X>>1;
 8             if(!ch[u][c])
 9             {
10                 memset(ch[sz],0,sizeof(ch[sz]));
11                 ch[u][c]=sz;
12                 sz++;
13             }
14             val[u]++;
15             dp[u]=dep;
16             dep++;
17             f[ch[u][c]]=u;
18             u=ch[u][c];
19         }
20         return u;
21     }

写残的Code【雾

AC Code：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 #define LL long long
 7 #define MOD 998244353;
 8 LL bit[30];
 9 
10 int a[100010];
11 LL ans ;
12 int T;
13 
14 struct Trie{
15     int next[30*50010][2];
16     int num[30*50010];
17     int root,tot;
18     int newnode(){
19         num[tot] = 0;
20         next[tot][0] = next[tot][1] = -1;
21         tot++;
22         return tot-1;
23     }
24     void init(){
25         tot = 0;
26         root = newnode();
27     }
28     void insert(int val){
29         int now = root;
30         for(int i = 0;i < 30;i++){
31             int id;
32             if(val&bit[i])id = 1;
33             else id = 0;
34             if(next[now][id^1] != -1){
35                 //ans += (num[next[now][id^1]]<<i)%MOD;
36                 ans += (long long)bit[i]*num[next[now][id^1]]%MOD;
37                 ans %= MOD;
38             }
39             if(next[now][id] == -1)
40                 next[now][id] = newnode();
41             now = next[now][id];
42             num[now]++;
43         }
44     }
45 }tree;
46 
47 int main()
48 {
49     bit[0] = 1;
50     for(int i = 1;i < 30;i++)
51         bit[i] = 2*bit[i-1];
52 
53     cin>>T;
54     for(int TT=1;TT<=T;TT++)
55     {
56         int n;
57         cin>>n;
58         ans = 0;
59         tree.init();
60         for(int i = 1;i <= n;i++)
61         {
62             scanf("%d",&a[i]);
63             tree.insert(a[i]);
64         }
65         ans = ans*2%MOD;
66         printf("Case #%d: %I64d
",TT,ans);
67     }
68     return 0;
69 }

View Code