2015年女排世界杯|世界杯预测|16趣谈世界杯欢乐站|16joke.com

题面看这里

题目大意

给出 \(n\) 份答卷，每份答卷上有 \(m\) 个问题，每个问题的答案是 \(A~or~B\)。

定义一个问题子集是可辩别的，当且仅当该集合非空，且有大于等于 \(k\) 对答卷在该问题子集上的答案是不完全相同的。

问你可辩别的问题子集数量。

\((1 \le n \le 2 \times 10^5,~1 \le m \le 20,~1 \leq k \leq \frac{n(n-1)}{2})\)

题目分析

数据范围 \(1\leq m\leq20\)，一看就知道是个位运算的题，很自然地想到把答卷转化为01串，方便用各种位运算集合操作枚举状态和贡献。

考虑从 \(n\)​ 份答卷种取出任意的两份答卷作为一对，有 \(\dfrac {n*(n-1)}2\)​ 对答卷，每对答卷的状态都可以用一个十进制数 \(S\in[0,2^m-1]\)​ 来表示（\(S\)​ 也可以看作是一个集合），\(S\)​ 在二进制下第 \(i\)​ 位：为 0 代表这两份答卷的第 \(i\)​ 题答案相同；为 1 则代表答案不同。

对于每对答卷 \(S\)​，它能对哪些问题子集造成贡献？我们用一个十进制数 \(T\in[1,2^m-1]\)​ 来表示一个问题子集，\(T\)​ 在二进制下第 \(i\)​ 位：为 0 代表第 \(i\)​ 个问题不在 \(T\)​ 这个问题子集中；为 1 则代表在 \(T\)​ 中。显然如果有 \(S\cap T\neq\varnothing\)​，则 \(S\)​ 能对 \(T\)​ 造成一点贡献。举个栗子：

\(m=3\)，则 \(T\in\{001,010,011,100,101,110,111\}\)，如果有一个 \(S=2=(010)_2\)，则代表有一对答卷第 1 题（下标从 0 开始）的答案不同，那么当取 \(T\in\{010,011,110,111\}\) 时，\(S\) 能够算作一对“在该问题子集上的答案不完全相同的答卷”，即造成一点贡献。

至此，一个很暴力的思路就出来了，枚举每个 \(T\in[1,2^m-1]\)，同时暴力枚举每对答卷的状态 \(S\)，判断是否存在 \(k\) 个以上的 \(S\) 交 \(T\) 不为空，如果存在，则 ans++，代码如下：

for(int t=1;t<1<

int cnt=0;

for(int i=1;i<=n;i++){ //双重循环枚举S

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

int s=a[i]^a[j];

if(s&t) cnt++; //两个数与起来 相当于求交集

}

}

if(cnt>=k) ans++;

}

时间复杂度 \(O(n^2*2^m)\)，必炸。

考虑利用位运算优化，显然双重循环枚举 \(S\) 的时间复杂度过高，必须优化，怎么做呢？

显然一个 \(S\) 可能会由多对答卷组成，因此我们定义一个 \(F(S)\) 数组：

\[F(S)=\sum_{i=1}^n\sum_{j=i+1}^n~\Big[a[i]\oplus a[j]=S\Big]

\]

\(F(S)=x\) 表示有 \(x\) 对答卷的状态为 \(S\)。

用一个十进制数 \(i\in[0,2^m-1]\)​ 来表示单独一张答卷的状态，\(i\)​ 二进制下第 \(j\)​ 位：为 0 代表这张答卷的第 \(j\)​ 题答案为 \(A\)​；为 1 则代表答案为 \(B\)​。定义一个桶数组 num[i]，表示状态为 \(i\)​ 的答卷的数量，那么可以得到：

\[F(S)=\dfrac 12\sum_{i\oplus j=S}~num[i]*num[j]

\]

这个形式我们就很熟悉了，裸的 FWT，我们可以在 \(O(m*2^m)\) 时间内求出 \(F(S)\) 数组，注意到 \(i=j\) 是非法情况，这样的情况总共会出现 \(n\) 次，此时 \(i\oplus j=0\)，因此还应将 FWT 后求得的 \(F(0)\) 减去 \(n\)。

再定义一个 \(G(T)\) 数组：

\[G(T)=\sum_{T\cap S\neq\varnothing}F(S)

\]

\(G(T)=x\) 代表当问题子集为 \(T\) 时，共有 \(x\) 对答卷能造成贡献，则 \(ans=\sum~[G(T)\geq k]\)。

发现 \(G(T)\) 并不好求，因为 \(\sum\limits_{T\cap S\neq\varnothing}F[S]\) 没啥好方法能够直接求出，只能暴力枚举。

于是我们做个容斥，定义 \(G(T)=x\) 代表当问题子集为 \(T\) 时，有 \(x\)​​ 对答卷不能造成贡献，则有：

\[G(T)=\sum_{T\cap S=\varnothing}F(S)=\sum_{S\subseteq(U-T)}F(S)

\]

这里 \(U\)​​​​​​ 是全集，用十进制数表示就是 \(2^m-1\)​​​​​​，即 \(G(T)\)​​​​ 计算的是 \(F(T 的补集的子集)\) ​​所造成的贡献之和，这也是老套路了，可以用 SOSdp 在 \(O(m*2^m)\)​​ 时间内求出 \(G\)​​​​​​​ 数组，具体写法看下面的代码实现。

于是对于每个问题子集 \(T\)​​​​，有 \(G(T)\)​​​​ 个不能造成贡献的，则能造成贡献的有 \(\dfrac {n*(n-1)}{2}-G(T)\)​​​​ 个，因此 \(ans=\sum~[\dfrac {n*(n-1)}{2}-G(T)\geq k]\)​​​​。

在 \(O(m*2^m)\)​ 的时间里预处理出 \(F\)​ 数组和 \(G\)​ 数组，最后再 \(2^m\)​ 次枚举计算答案，总时间复杂度 \(O(m*2^m)\)​。

代码实现

#include

using namespace std;

const int maxn=3e6+6;

long long n,m,k,limit,ans;

long long f[maxn],g[maxn];

void fwt(long long *a,int type,int limit){

for(int i=1;i

for(int j=0,step=i<<1;j

for(int k=0;k

long long x=a[j+k],y=a[j+k+i];

a[j+k]=x+y,a[j+k+i]=x-y;

if(type==-1) a[j+k]/=2,a[j+k+i]/=2;

}

}

}

}

int main(){

ios::sync_with_stdio(false);

cin >> n >> m >> k;

limit=1<

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

long long d=0,p=1;

char now;

for(int j=0;j

cin >> now;

now-='A';

d+=p*now; //把字符串转化为01串 相当于一个二进制数 再转化为一个十进制数 即分析里的答卷状态i

}

f[d]++; //这里的f还只是分析的桶数组num 等执行完fwt操作后才变成了f

}

fwt(f,1,limit);

for(int i=0;i

f[i]*=f[i];

}

fwt(f,-1,limit);

f[0]-=n; //去掉 i=j 的情况

limit--;

for(int i=0;i<=limit;i++){ //初始化g数组 显然f[i的补集]会对g[i]造成贡献

g[i]=f[i^limit]/2; //与全1的数进行异或 相当于求补集 即i^limit是i的补集

}

for(int i=0;i

for(int j=0;j<=limit;j++){

if(1<

int k=1<

g[k]+=g[j]; //g[j]会对g[k]造成贡献

}

}

}

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

if(n*(n-1)-2*g[i]>=k*2) ans++;

}

cout << ans;

}

FWT 纯纯的套路，套板子就行，没什么好说的。其实是不会说

这里稍微说下 SOSdp：

for(int i=0;i<=limit;i++){ //初始化g数组 显然f[i的补集]会对g[i]造成贡献

g[i]=f[i^limit]/2; //与全1的数进行异或 相当于求补集 即i^limit是i的补集

}

for(int i=0;i

for(int j=0;j<=limit;j++){

if(1<

int k=1<

g[k]+=g[j]; //g[j]会对g[k]造成贡献

}

}

}

这里我们要求的是补集的子集的贡献之和，而初始化时，我们让 g[i]=f[i^limit]/2，则问题转化为了求 \(G(T)\) 的超集的贡献之和，这一步可能有点抽象，举个栗子帮忙理解一下：

\(m=3,~T=2=(010)_2\)，则 \(G(T)=F(101)+F(100)+F(001)+F(000)=G(010)+G(011)+G(110)+G(111)\)。

然后就是 SOSdp 求超集之和了。这里的 \(j\)​​​​​​​​​ 枚举了每个问题子集，遍历 \(i\)​​​​​​​ 从 \(0\sim m-1\)​​​​​ 从而枚举每个 \(j\)​​​​​​​ 的每一位。

如果 \(j\)​​​​​​​​ 的第 \(i\)​​​​​​​​ 位为 1，则 g[k]+=g[j]。什么意思呢？令 \(k=1<

这样计算贡献显然是不重不漏的，因为我们是从小到大枚举的，且每个集合都只对跟它只有一位不同的集合造成贡献。