题目
题目描述
不放图了烦死
给定$N$个长度都为$M$的字符串，每个字符为小写字母或?，求能与其中$K$个字符串匹配的字符串$T$个数，要求$T$由小写字母组成，?与所有字符匹配
输入输出格式
输入格式：
本题包含多组数据。 第一行：一个整数T，表示数据的个数。 对于每组数据： 第一行：两个整数，N和K（含义如题目表述）。 接下来N行：每行一个字符串。
输出格式：
如题
输入输出样例
输入样例#1：
5
3 3
???r???
???????
???????
3 4
???????
?????a?
???????
3 3
???????
?a??j??
????aa?
3 2
a??????
???????
???????
3 2
???????
???a???
????a??
输出样例#1：
914852
0
0
871234
67018
说明
对于30%的数据，T ≤ 5，M ≤ 5，字符串长度≤ 20；
对于70%的数据，T ≤ 5，M ≤ 13，字符串长度≤ 30；
对于100%的数据，T ≤ 5，M ≤ 15，字符串长度≤ 50。
题解
直接状压，枚举匹配到的位数、匹配状态和该位用什么字符匹配
开始同一位的计数器没清零WA了一发……
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=3.3e4+5,mod=1000003;
int T,n,k,m,ans;
int f[51][MAX],qwq[51][27],cnt[51];
char a[15][51];
int GET_NUM(int x)
{
int num=0;
while(x) x&=(x-1),++num;
return num;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
memset(f,0,sizeof(f));
memset(cnt,0,sizeof(cnt));
memset(qwq,0,sizeof(qwq));
for(int i=0;i<n;++i)
scanf("%s",a[i]+1);
m=strlen(a[0]+1),ans=0;
for(int i=1;i<=m;++i)
for(int j=0;j<n;++j)
if(isalpha(a[j][i]))
{
if(!qwq[i][a[j][i]-'a']) ++cnt[i];
qwq[i][a[j][i]-'a']|=(1<<j);
}
else qwq[i][26]|=(1<<j);
f[0][(1<<n)-1]=1;
for(int i=1;i<=m;++i)
{
for(int S=0;S<(1<<n);++S)
{
for(int j=0;j<26;++j)
if(qwq[i][j]) (f[i][(qwq[i][j]|qwq[i][26])&S]+=f[i-1][S])%=mod;
if(qwq[i][26]) (f[i][qwq[i][26]&S]+=(26-cnt[i])*f[i-1][S])%=mod;
}
}
for(int i=0;i<(1<<n);++i)
if(GET_NUM(i)==k) (ans+=f[m][i])%=mod;
printf("%d\n",ans);
}
}
