一般n比较大，状态数m（这里10）比较小时适合状态压缩成0...1到111..1这样1<<m个状态！！！ 也就是暴力枚举所有子集~
ac代码：
#include<bits/stdc++.h> #define per(i,a,b) for(int i=a;i<=b;i++) using namespace std; typedef long long ll; const int mod=998244353; const int inf =0x3f3f3f; const double eps=1e-8; #define siz 1100 int n,m,k,dp[siz][siz],vis[siz];//vis表示在i之前状态为j的数量 char ss[siz][11]; int s[siz][11]; int main() { int T; scanf("%d",&T); int cas=0; while(T--){ cas++; scanf("%d%d%d",&n,&m,&k); per(i,1,n)scanf("%s",ss[i]); memset(s,0,sizeof(s)); per(i,1,n)per(j,0,m-1)if(ss[i][j]=='A')s[i][j]=1; for(int st=1;st<(1<<m);st++){ memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ int state=0; for(int j=0;j<m;j++){ //printf("%d %d %d ",st,1<<j,s[i][1j]);// if(st&(1<<j)&&s[i][j]) state|=(1<<j); } vis[state]++; dp[i][st]=dp[i-1][st]+i-vis[state]; } } int ans=0; per(i,1,(1<<m)){if(dp[n][i]>=k)ans++;} printf("Case #%d: %d ",cas,ans); } return 0; }