题目概述

United in Stormwind

解题报告

太久没做过这种题了，其实非常套路。

题目里给出了 $n$ 个 $01$ 串，把两个串异或就可以得到两个串不同位置的集合。首先我们可以利用FWT求出 $cnt_i$ 表示异或值为 $i$ 的对数，然后考虑怎么计算答案。

对于一种方案 $S$ ，如果 $S\ and\ i\not=0$ ，说明 $S$ 和 $i$ 有交集，即 $cnt_i$ 都符合至少存在 $S$ 中的一位不同。那么：

$$ sum_S=\sum_{S\ and\ i\not=0}cnt_i $$

但是这东西不好处理，考虑补集转化，我们用 ${n\choose 2}$ 减去 $S\ and\ i=0$ 的方案数。

然后这就是经典的高维前缀和，$S\ and\ i=0$ 可以转化为 $\bar S\ and\ i=i$ 即 $i$ 是 $\bar S$ 的子集。

最后看 $sum_S\ge K$ 有多少个就行了。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxm=20,maxs=1<<20;

int n,m,ans;LL K,A[maxs+5];char s[maxm+5]; 

void FWT(LL *a,int n,int f){
    for (int k=1;k<n;k<<=1)
        for (int i=0;i<n;i+=k<<1)
            for (int j=0;j<k;j++){
                LL x=a[i+j],y=a[i+j+k];
                a[i+j]=x+y;a[i+j+k]=x-y;
                if (f<0) a[i+j]/=2,a[i+j+k]/=2;
            }
}
int main(){
    scanf("%d%d%lld",&n,&m,&K);
    for (int i=1;i<=n;i++){
        scanf("%s",s);int S=0;
        for (int i=0;i<m;i++) if (s[i]=='B') S|=1<<i;
        A[S]++;
    }
    FWT(A,1<<m,1);
    for (int i=0;i<(1<<m);i++) A[i]=A[i]*A[i];
    FWT(A,1<<m,-1);
    A[0]-=n;for (int i=0;i<(1<<m);i++) A[i]/=2;
    for (int i=0;i<m;i++)
        for (int s=0;s<(1<<m);s++)
            if (s>>i&1) A[s]+=A[s^(1<<i)];
    LL tot=(LL)n*(n-1)>>1;
    for (int i=1;i<(1<<m);i++) if (tot-A[i^((1<<m)-1)]>=K) ans++;
    printf("%d\n",ans);
    return 0;
}