ZYB loves Xor I
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 655 Accepted Submission(s): 289
Problem Description
Memphis loves xor very musch.Now he gets an array A.The length of A is n.Now he wants to know the sum of all (lowbit(Ai xor Aj )) (i,j∈[1,n])
We define that lowbit(x)=2k ,k is the smallest integer satisfied ((x and 2k )>0)
Specially,lowbit(0)=0
Because the ans may be too big.You just need to outputans mod 998244353
We define that lowbit(x)=
Specially,lowbit(0)=0
Because the ans may be too big.You just need to output
Input
Multiple test cases, the first line contains an integer T(no more than 10), indicating the number of cases. Each test case contains two lines
The first line has an integern
The second line hasn integers A1 ,A2 ....An
n∈[1,5∗104] ，Ai∈[0,229]
The first line has an integer
The second line has
Output
For each case, the output should occupies exactly one line. The output format is Case #x: ans, here x is the data number begins at 1.
Sample Input
2 5 4 0 2 7 0 5 2 6 5 4 0
Sample Output
Case #1: 36
Case #2: 40
膜拜一下出题的skydec大爷（链接->http://skydec.is-programmer.com/），膜拜一下背景主人公ZYB。。
这题要求任意两个数xor以后的lowbit，我们可以知道对于任意两个数a，b，lowbit(a xor b) = 2^k，k是两个数二进制位最后不同的位数，因为这个性质我们可以用Tire求解。
用所有数的二进制从后向前构造Tire，每一个节点记一下有多少个数，然后对每个数按位处理，每一次ans+=从这位起开始不同的数的个数*2^层数。意思就是对于每一位进行分治，不懂的可以模拟程序运行。
#include <cstdio>
#include <cstring>
using namespace std;
const int mod = 998244353;
int tire[1000010][2],cnt,num[50010],ans,count[1000010],T,n;
void Insert(int val){
int now = 0;
for (int i=0;i<30;i++,val>>=1){
if (tire[now][val&1]) {now = tire[now][val&1];count[now]++;}
else {
tire[now][val&1] = ++cnt;
now = cnt;count[now] = 1;
}
}
}
int Query(int val){
int now = 0,res = 0;
for (int i=1;i<=30;i++,val>>=1){
int next = tire[now][val&1],other = tire[now][(val&1)^1];
if (other) (res+=count[other]*(1<<(i-1)))%=mod;
now = tire[now][val&1];
}
return res;
}
int main(){
scanf("%d",&T);
for (int C=1;C<=T;C++){
memset(tire,0,sizeof(tire));
cnt = 0;ans = 0;
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d",&num[i]);
Insert(num[i]);
}
for (int i=1;i<=n;i++)
(ans+=Query(num[i]))%=mod;
printf("Case #%d: %d\n",C,ans);
}
}
评论 (0)
