hdu 5269 ZYB loves Xor I && BestCoder Round #44
amp HDU round 44 XOR loves
2023-09-11 14:20:43 时间
题意:
ZYB喜欢研究Xor,如今他得到了一个长度为n 的数组A。于是他想知道:对于全部数对
(i,j)(i∈[1,n],j∈[1,n]) 。lowbit(AixorAj) 之和为多少.因为答案可能过大,你须要输出答案对998244353取模后的值 定义lowbit(x)=2k ,当中k是最小的满足(x and 2k)>0 的数 特别地:lowbit(0)=0
输入描写叙述
一共T (T≤10 )组数据,对于每组数据: 第一行一个正整数n ,表示数组长度 第二行n 个非负整数,第i 个整数为Ai n∈[1,5∗104] ,Ai∈[0,229]
输出描写叙述
每组数据输出一行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官方题解:
我们考虑,当A xor B 的答案为2p 时,A 和B 表示成二进制数后末p−1 位肯定同样
于是我们维护一颗字母树。将每一个数表示成二进制数后翻转能够下。插入字母树
统计答案时,我们找出Ai 的二进制数翻转后在字母树上的路径,对于路径上每一个点x 。设他走的边是v 。且当前为
第k 位,则和他xor 后lowbit为2k 的数的个数为trans(x,v^1)的子树大小。
trans(x,v)表示字母树上在结点x,走连出去的字母为v的边到达的结点
时间复杂度:O(nlogA)
总结:
1.这道题一直拖着没有写总结,感觉一直没有从变化中观察到不变
2.当时自己比赛没有做出来这个题目,可能当时校赛得了第7。导致有些自负吧,事实上还是能力的不足,好的行为并没
有培养成好的习惯。
3.后来也是看了一眼bc群上的说trie,才想到的。以下总结一下失败的原因吧。
4.我開始是想对于除0以外的数按lowbit值排序(也就是最低位出现的1排序),lowbit同样的再依照除此位的lowbit排
序,没搞出来。
5.假设刚才的思路清晰之后,事实上就是分层处理,按lowbit值同样的为一组,对于不同组直接能够算出,对于同组,减
掉刚才的lowbit。再求lowbit。继续分组运算。
6.这不就是不停地分层处理吗?!
那能够用trie这样的数据结构直接来做
7.比赛时候没有把算法考虑清楚就急忙写代码,以后不许再犯同样的大忌了
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; typedef long long LL; #define MAXN 5000500 #define lowbit(i) ((i) & (-(i))) #define MOD 998244353 struct Trie { int ch[MAXN][2],val[MAXN],cnt; LL ans; void init() { ans = cnt = val[0] = ch[0][0] = ch[0][1] = 0; } void insert(int v) { val[0]++; int deep = 0,num = val[0],next = 0; for(int i = 0;i < 30;i++) { int c = v & 1; if(!ch[next][c]) { ch[next][c] = ++cnt; val[cnt] = ch[cnt][0] = ch[cnt][1] = 0; } val[ch[next][c]]++; deep++; ans += ((num - val[ch[next][c]]) << deep); ans %= MOD; next = ch[next][c]; v >>= 1; num = val[next]; } } }trie; int main() { int _,n,cur; for(int kcas = scanf("%d",&_);kcas <= _;kcas++) { trie.init(); for(int i = scanf("%d",&n);i <= n;i++) { scanf("%d",&cur); trie.insert(cur); } printf("Case #%d: %I64d\n",kcas,trie.ans); } }
相关文章
- HDU 5304(Eastest Magical Day Seep Group's Summer-环加外向树生成树计数)[Template:Kirchhoff矩阵]
- C#高级编程(第9版) -C#5.0&.Net4.5.1 书上的示例代码下载链接
- HDU 4738 Caocao's Bridges(找割边)
- 解决 Property 'sqlSessionFactory' or 'sqlSessionTemplate' are required
- python中lambda实现赋值和多语句 & 单行命令行中执行多语句
- HDU 1513 && POJ 1159 Palindrome (DP+LCS+滚动数组)
- 《C++ AMP:用Visual C++加速大规模并行计算》——3.7 使用restrict(amp)标记的函数
- 计算机网络实验(Wireshark、WinPcap 编程、协议分析&流量统计)【100010393】
- (数据科学学习手札24)逻辑回归分类器原理详解&Python与R实现
- "转成"
- 【排序算法(三)】交换排序(冒泡排序&&快速排序)
- hdu 1165 Eddy's research II(数学题,递推)
- hdu 4122 Alice's mooncake shop (线段树)
- 乞讨 间隔[a,b]在见面p^k*q*^m(k>m)中数号码
- POJ1789&ZOJ2158--Truck History【最小生成树变形】