一道很妙的状压dp，差不过做过才会，数组设置的很妙也很难
我们对 T 字符串进行考虑
首先T字符串每一位 只能是小写字母。
所以我们可以先预处理 T字符串每一位 为某个小写字母时，对应到S字符串集里面，能匹配那些S字符
令f[ i ][ j ]为T字符串第 i 位，为 j 小写字母时，对应到S字符串集能有多少匹配的
这可以预处理出来
然后考虑状压dp：
令dp[i][j]为到了第i位，成功匹配的状态为j时的方案数，这样令的原因是容易转移
转移:dp[i][j&(f[i][k])]+=dp[i-1][j] （在第i位选 0~26 字母）
最后统计：popcount(i)==m , ans+=dp[len][i]
Code:
#include<bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define popb pop_back #define fi first #define se second const int N=55; const int M=16; const int MOD=1000003; //const int inf=0x3f3f3f3f; //const ll INF=0x3ffffffffffff; int T,n,m,f[N][30],dp[N][1<<M]; char s[N][N]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } int main() { // freopen("","r",stdin); // freopen("","w",stdout); T=read(); while(T--) { n=read(),m=read(); for(int i=0;i<n;i++) scanf("%s",s[i]+1); int len=strlen(s[0]+1); for(int i=1;i<=len;i++) for(int j=0;j<26;j++) for(int k=0;k<n;k++) if(s[k][i]=='?'||s[k][i]=='a'+j) f[i][j]|=(1<<k); int ans=0; // for(int i=0;i<26;i++) dp[1][f[1][i]]++; dp[0][(1<<n)-1]=1; for(int i=1;i<=len;i++) for(int j=0;j<(1<<n);j++) { // if(!dp[i][j]) continue; for(int k=0;k<26;k++) dp[i][f[i][k]&j]=(dp[i][f[i][k]&j]+dp[i-1][j])%MOD; } for(int i=0;i<(1<<n);i++) if(__builtin_popcount(i)==m) ans=(ans+dp[len][i])%MOD; printf("%d\n",ans); for(int i=0;i<=len;i++) for(int j=0;j<26;j++) f[i][j]=0; for(int i=0;i<=len;i++) for(int j=0;j<(1<<n);j++) dp[i][j]=0; } return 0; }