看数据范围就知道应该要状压，也不难看出应该压缩位数的状态。所以设f[i][j]为前i位，相互匹配的字符串的状态。
那么，就会有 f[i+1][j&a[i][ch]]=(f[i+1][j&a[i][ch]+f[i][j])%mod。
其中a[i][j]表示满足第i位为j所对应的字母的字符串的状态。
所以只要枚举长度为l（其中一个字符串的长度）时的状态，并检查一下当前状态下匹配的字符串的个数是否为k，再更新答案。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=16,M=51;
#define mod 1000003
int n,m,k,i,j,T,ans,f[M][(1<<N)],a[M][26];
//a[i][j]代表第i位为字母j+'0'的字符串的集合（状态）；
//f[i][j]表示前i位，状态为j时答案个数；
string s[N];
int main(){
scanf("%d",&T);
while(T--){
ans=0;
memset(f,0,sizeof f);
memset(a,0,sizeof a);
scanf("%d%d",&n,&k);
// cout<<"lksbvc"<<endl;
for(i=1;i<=n;i++)cin>>s[i];
// cout<<"!"<<endl;
int l=s[1].length();
for(i=0;i<l;i++){
for(char ch='a';ch<='z';ch++){
for(j=1;j<=n;j++){
if(s[j][i]=='?'||s[j][i]==ch)
a[i][ch-'a']|=(1<<j-1);
}
}
}
f[0][(1<<n)-1]=1;
for(i=0;i<l;i++){
for(j=0;j<(1<<n);j++){
if(f[i][j]){
for(char ch='a';ch<='z';ch++){
f[i+1][(j&a[i][ch-'a'])]=(f[i+1][(j&a[i][ch-'a'])]+f[i][j])%mod;
}
}
}
}
for(i=0;i<(1<<n);i++){
int tot=0;
for(j=1;j<(1<<n);j<<=1)if(i&j)tot++;else if(tot>k)break;
if(tot==k)ans=(ans+f[l][i])%mod;
}
printf("%d\n",ans);
// cout<<"!"<<endl;
}
return 0;
}