题目

Problem Description

ZYB喜欢研究Xor，现在他得到了一个长度为n的数组A。于是他想知道：对于所有数对(i,j)(i∈[1,n],j∈[1,n])，lowbit(Ai xor Aj)之和为多少.由于答案可能过大，你需要输出答案对998244353取模后的值 定义lowbit(x)=2^k，其中k是最小的满足(x and 2^k)>0的数 特别地：lowbit(0)=0

Input

第一行一个正整数n，表示数组长度 第二行n个非负整数，第i个整数为Ai n∈[1,5∗10^4]，Ai∈[0,2^29]

Output

输出一个整数ans。

Sample Input

5 4 0 2 7 0

Sample Output

36

分析

题意就是问一堆数中两两异或值的 lowbit 和。根为最低位，建一棵字典树，然后对于每个节点，在它两个分支中各取一个（存在的）数，它们的异或值肯定是当前节点的下一位（因为前面都一样），利用这个求出所有节点对答案的贡献即可。

程序

#include <cstdio> #define Ha 998244353 #define L(x) (l[x]?l[x]:(l[x]=++N)) #define R(x) (r[x]?r[x]:(r[x]=++N)) long long n,k,A,i,j,N=1,ans,l[1500000],r[1500000],v[1500000]; void dfs(int x,long long o){ ans=(ans+v[l[x]]*v[r[x]]*o)%Ha; if (l[x]) dfs(l[x],o<<1); if (r[x]) dfs(r[x],o<<1); } int main(){ scanf("%lld",&n); for (i=1; i<=n; i++){ scanf("%lld",&A); for (v[k=1]++,j=0; j<=29; j++){ if (A&(1<<j)) v[k=R(k)]++; else v[k=L(k)]++; } } dfs(1,1); printf("%lld",(ans*2)%Ha); }