Preface

先补一下这周一队友VP的ICPC2020沈阳，这场由于我在补作业+晚上有大物实验，因此只参与了中间一个多小时，纯口胡了几个简单题

因为我没怎么参与所以过的其它题就不写补题+写博客了，~~毕竟队友会等于我会~~

那么就主要把我比赛时看了但没啥思路的M补了，AI祁神好像在补那我就不管了，后面好像还有个J是个DS到时候也抽时间补一下

Solution

回到这题，其实就是把两个很套路的东西结合在一起了，前半部分其实很容易想到

但由于我一直不会sosdp，所以以为后面的只能枚举子集\(O(3^m)\)就做不动了，后面去看了下sosdp好像是个很简单的玩意来着

首先我们不妨把每个人的回答看作一个数\(\{a_i\}\)，那么\(a_u\oplus a_v\)就代表\(u,v\)两人在哪些问题上回答不同

那么我们显然可以用一个FWT先求出异或和为某个数的人的对数

考虑直接枚举最后答案的集合\(S\)，设满足题意的pair得到的异或和为\(T\)，则当\(S\cap T\ne \emptyset\)时这个pair可以造成贡献

直接统计不为空集的方案不好算，我们容斥一下用\(C_n^2\)减去\(S\cap T=\emptyset\)的贡献，这个又等价于\(T\subset C_S\)

用sosdp或者FMT优化下这个子集卷积即可，总复杂度\(O(m\times 2^m)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1<<20;
int n,m,k,lim,x,a[N],b[N],f[N],all,ans; char s[30];
inline void FWT_XOR(int* f,CI opt)
{
	for (RI i=1,j,k;i<lim;i<<=1) for (j=0;j<lim;j+=(i<<1)) for (k=0;k<i;++k) 
	{
		int x=f[j+k],y=f[i+j+k]; f[j+k]=x+y; f[i+j+k]=x-y;
		if (!~opt) f[j+k]/=2,f[i+j+k]/=2;
	}
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%lld%lld%lld",&n,&m,&k),lim=1<<m,i=0;i<n;++i)
	{
		int cur=0; for (scanf("%s",s),j=0;j<m;++j)
		cur=(cur<<1)+(s[j]=='A'); ++a[cur]; ++b[cur];
	}
	for (FWT_XOR(a,1),FWT_XOR(b,1),i=0;i<lim;++i) a[i]*=b[i];
	for (FWT_XOR(a,-1),a[0]-=n,i=0;i<lim;++i) a[i]/=2,f[i]=a[i];
	for (j=0;j<m;++j) for (i=0;i<lim;++i) if ((i>>j)&1) f[i]+=f[i^(1<<j)];
	for (all=1LL*n*(n-1)/2LL,i=0;i<lim;++i)
	if (all-f[(lim-1)^i]>=k) ++ans;
	return printf("%lld",ans),0;
}