UnitedinStormwind

The first line contains three integers ${n, m, k}$ $(1 \le n \le 2 \times 10^5, 1 \le m \le 20, 1 \leq k \leq \frac{n(n-1)}{2})$ , as specified in the problem statement.

Each of the following ${n}$ lines contains a string of length ${m}$ , which contains only ${A}$ and ${B}$ , indicating the answer to each question in the referendum results.

C++ 解法, 执行用时: 113ms, 内存消耗: 16836K, 提交时间: 2022-02-06 11:34:52

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=(1<<20)+5; 
int n,m,x,ans;
ll k,c[N],f[N];
char s[N];
void FWTxor(ll f[N],int n,int op){
	ll x,y;
	for(int k=2;k<=n;k<<=1)
		for(int i=0,m=k>>1;i<n;i+=k)
			for(int j=i;j<i+m;j++){ 
				x=f[j],y=f[j+m],f[j]=x+y,f[j+m]=x-y;
				if(op==-1) f[j]/=2,f[j+m]/=2;
			} 
}
signed main(){
	scanf("%d%d%lld",&n,&m,&k);
	for(int i=1;i<=n;i++){
		scanf("%s",s+1),x=0;
		for(int j=1;j<=m;j++) x|=(s[j]=='A')<<(j-1);
		c[x]++; 
	}
	FWTxor(c,(1<<m),1);
	for(int i=0;i<(1<<m);i++) f[i]=c[i]*c[i];
	FWTxor(f,(1<<m),-1);
	for(int i=0;i<m;i++)
		for(int j=0;j<(1<<m);j++)
			if((j>>i)&1) f[j]+=f[j^(1<<i)];
	for(int i=0;i<(1<<m);i++) ans+=(1ll*n*n-f[i]>=k*2);
	printf("%d\n",ans);
	return 0;
}

详情