题意描述
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 output ans mod 998244353
求每个数和其他数异或后的lowbit之和
思路
由于异或的性质可知，只要找到一组两数第x位二进制不同的数，那么就找到了两数异或的第一个1，也就是lowbit的值。所以我们可以使用一个cnt数组来维护某一位出现的次数，如果在遍历的时候找到了一个点，就计算一次答案。
AC代码
代码语言：javascript复制#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long LL;
const int N=31*1e5 10;
const int M=150;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
int Case=1;
LL bit[35],ans=0;
struct trie{
int tot,root,child[N][2],cnt[N];
bool flag[N];
void init(){
memset(child[1],0,sizeof child[1]);
memset(cnt,0,sizeof cnt);
flag[1]=false;
tot=root=1;
}
void Insert(int u){
int cur=root;
for(int i=0;i<=30;i ){
int t=u>>i&1;
if(!child[cur][t]){
child[cur][t]= tot;
memset(child[tot],0,sizeof child[tot]);
flag[tot]=false;
}
if(child[cur][t^1]) ans =bit[i]*cnt[child[cur][t^1]]%MOD;
cur=child[cur][t];
cnt[cur] ;
}
}
};
void solve(){
int n;scanf("%d",&n);
ans=0;
trie tr;
tr.init();
for(int i=0;i<n;i ){
int x;scanf("%d",&x);
tr.Insert(x);
}
ans=ans*2%MOD;
printf("Case #%d: %dn",Case ,ans);
}
int main(){
//IOS;
bit[0]=1;
for(int i=1;i<=30;i ) bit[i]=bit[i-1]*2;
int t;scanf("%d",&t);
while(t--){
solve();
}
return 0;
}
