2026-07-26 07:10:27

2020 ICPC 沈阳站 M. United in Stormwind

题意：有m个问题，n份长度为m的答卷，每个答案都是A或者B

现在要任选一个问题的子集，如果大于等于k对答卷在该子集上答案有不同，就说这个子集是可辩别的

求可辩别的子集数量

首先将答卷转为01串，那么两个答卷相同就等价于两个01串异或为0

对于一个问题的子集S，先考虑计算异或等于S的01串对数量，即

\[\rm F(S)= \sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}[ans_i \oplus ans_j=S]

\]

我们用一个桶数组num[S]表示等于S的01串数量，那么F可以写为

\[\rm F(S)= \dfrac{1}{2}\sum\limits_{i\oplus j=S}num[i]*num[j]

\]

这是FWT的标准形式，可以在\(\rm O(m2^m)\)的时间求出F数组

我们实际要求的集合T， 只要和S有交，就可以被F(S)贡献

因而有

\[\rm G(T) = \sum\limits_{S \cap T\not=\emptyset}F(S)

\]

简单容斥一下，有

\[\rm G(T) = \dfrac{n*n}{2}-\sum\limits_{S \cap T=\emptyset}F(S)

\]

这里的\(S\cap T=\emptyset\) 等价于 \(S\subseteq U-T\)，枚举子集\(3^m\)转移不可取

实际上这是在CF上考多次的SOS模型，可以用DP在\(\rm O(m2^m)\)做

设dp[S][i]表示做完前i位，S的答案，转移考虑第i位是0还是1

如果第i位是0，直接从前面转移过来，即dp[S][i]=dp[S][i-1]

如果第i位是1，那么考虑这位可以为0或1，即dp[S][i]=dp[S][i-1]+dp[S^(1<

实际中第二维可以被压掉，因为从小往大枚举S时，转移的对象总是前面的

这样就做完了，\(ans=\sum\limits_{S}[n*n-2G(s)\geq2k]\)

#include

#define int long long

using namespace std;

int rd(){

int ret=0,f=1;char c;

while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;

while(isdigit(c))ret=ret*10+c-'0',c=getchar();

return ret*f;

}

// const int MOD = 998244353,INV2=499122177;

const double

Cor[2][2]={{1,0},{1,1}},

Cand[2][2]={{1,1},{0,1}},

Cxor[2][2]={{1,1},{1,-1}},

ICor[2][2]={{1,0},{-1,1}},

ICand[2][2]={{1,-1},{0,1}},

ICxor[2][2]={{0.5,0.5},{0.5,-0.5}};

void FWT(double *f,const double c[2][2],int n){

for(int len=1;len

for(int p=0;p

for(int i=p;i

double sav=f[i];

f[i]=(c[0][0]*f[i]+c[0][1]*f[i+len]);

f[i+len]=(c[1][0]*sav+c[1][1]*f[i+len]);

}

}

void bitmul(double *f,double *g,const double c[2][2],const double ic[2][2],int n){

FWT(f,c,n);//FWT(g,c,n);

for(int i=0;i

FWT(f,ic,n);

}

const int MAXN = 2200006;

int n,m,k;

double f[MAXN];

char s[50];

signed main(){

n=rd();m=rd();k=rd();

for(int i=1;i<=n;i++){

scanf("%s",s+1);

int tmp=0;

for(int j=1;j<=m;j++){

if(s[m-j+1]=='A') tmp|=(1<<(j-1));

}

f[tmp]+=1.0;

}

bitmul(f,f,Cxor,ICxor,1<

for(int i = 0; i < m; i++)

for(int j = 0; j < (1<

if(j & (1 << i)) f[j] += f[j ^ (1 << i)];

int ans=0;

for(int i=0;i<(1<

if(n*n-(long long)(f[i]+0.5)>=2*k) ans++;

}

cout<

return 0;

}