【SSLGZ】试卷

题目

思路

状压+组合计数
状压出选择那些试题，然后统计每种试卷的个数，最后两两相乘

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=2077;
int t,n,m,k,a[maxn],b[maxn],c[maxn];
char st[maxn];
int main()
{scanf("%d",&t);while(t--){memset(a,0,sizeof(a));int ans=0;scanf("%d%d%d",&n,&m,&k);for(int i=1; i<=n; i++){scanf("%s",st);for(int j=0; j<m; j++) a[i]=a[i]*2+(st[j]=='A');}int p=1<<m;for(int s=1; s<=p; s++){memset(b,0,sizeof(b)); int cnt=0,ss=0;memset(c,0,sizeof(c));for(int i=1; i<=n; i++){if(!b[a[i]&s]) c[++cnt]=a[i]&s;b[a[i]&s]++;}for(int i=1; i<=cnt-1; i++) for(int j=i+1; j<=cnt; j++) ss+=b[c[i]]*b[c[j]];if(ss>=k) ans++;}printf("%d\n",ans);}
}