[CS Academy] Maxor

CS Academy

思路

直接搞一个生成函数,自己卷自己,容斥一下

代码

#include <iostream>
#include <cstdio>

typedef long long LL;

int N;
LL f[1<<17], g[1<<17];

void fwt(LL *P, int opt){
	for(int i=1; i<(1<<17); i<<=1)
		for(int p=i<<1, j=0; j<(1<<17); j+=p)
			for(int k=0; k<i; k++)
				P[i+j+k]+=P[j+k]*opt;
}

int main(){
	int x;
	scanf("%d", &N);
	for(int i=1; i<=N; i++){
		scanf("%d", &x);
		f[x]++; g[x]++;
	}
	fwt(f, 1);
	for(int i=0; i<(1<<17); i++) f[i]=f[i]*f[i];
	fwt(f, -1);
	int ans=-1;
	for(int i=1; i<(1<<17); i++) if(f[i]-g[i])
		ans=i;
	printf("%d %lld\n", ans, (f[ans]-g[ans])/2);
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注