记录编号	456939	评测结果	AAAAAAAAAA
题目名称	求lowbit值之和	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.703 s
提交时间	2017-10-06 07:32:21	内存使用	114.73 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e7+10,p=998244353;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int mul(int x,int y){return (ll)x*y%p;}
int T,n,top,go[N][2],size[N],ans;
int New(){
	top++;
	go[top][0]=go[top][1]=size[top]=0;
	return top;
}
void insert(){
	int v;
	scanf("%d",&v);
	for (int i=0,p=1;i<31;i++){
		int w=(v>>i&1);
		if (!go[p][w]) go[p][w]=New();
		p=go[p][w];
		size[p]++;
	}
}
void dfs(int x,int h){
	ans=inc(ans,mul(mul(size[go[x][0]],size[go[x][1]]),1<<h));
	if (go[x][0]) dfs(go[x][0],h+1);
	if (go[x][1]) dfs(go[x][1],h+1);
}
int main()
{
	freopen("lowbit.in","r",stdin);
	freopen("lowbit.out","w",stdout);
	scanf("%d",&T);
	for (int i=1;i<=T;i++){
		top=ans=0;New();
		scanf("%d",&n);
		for (int i=1;i<=n;i++) insert();
		dfs(1,0);
		printf("Case #%d: %d\n",i,inc(ans,ans));
	}
	return 0;
}