题目传送门

思路

状态设计

像这种字符串匹配的题，状态设计里一定有一维代表目前匹配到了第 $i$ 位。
所以，我们设 $d{p}_{i,j}$ 表示目前 $T$ 串已经匹配到了第 $i$ 位，且匹配的 $S$ 串的状态为 $j$。

状态转移

假设现在状态为 $j$，我们就枚举下一个位置 $T_{i+1}$ 的可能的字符，然后看看有哪些 $S$ 串能匹配上。
假设能匹配的字符串的状态为 $x$，那么我们就可以转移 $d{p}_{i+1,j\&x}+=d{p}_{i,j}$。
这里 $j\&x$ 的意思就是，当前已经匹配第 $i$ 位的字符串中，还有哪些可以匹配上第 $i+1$ 位。

边界状态

边界状态是 $d{p}_{0,2^n-1}=1$。
那么为什么边界不是 $d{p}_{0,0}=1$ 呢？
因为如果由 $0$ 作为初始状态的话 $0\&x$ 会一直为 $0$，转移不到下一个状态。

答案统计

只需要枚举所有状态，然后看看有哪些状态中 $1$ 的个数恰好为 $k$，那就加入答案

时间复杂度

$O(T\times 26\times 2^n\times |S|)$

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 15 + 7;
const int maxs = (1 << 15) + 7;
const int mod  = 1000003;

int T, n, m, ns, len;
char s[maxn][57];
int mch[57][30];
int dp[57][maxs];
void solve() {
	memset(mch, 0, sizeof(mch));
	memset(dp, -1, sizeof(dp));  // 初始化成 -1, 因为一些状态可能转移不到 
	scanf("%d%d", &n, &m);
	ns = (1 << n) - 1;
	for (int i = 1; i <= n; ++i)
		scanf("%s", s[i] + 1);
	len = strlen(s[1] + 1);
	
	// 初始化一下, 看看第 i 位的字符为 ch 时能匹配的 S 串的状态
	for (int i = 1; i <= len; ++i)
		for (int ch = 1; ch <= 26; ++ch)
			for (int j = 1; j <= n; ++j)
				if (s[j][i] - 'a' + 1 == ch || s[j][i] == '?')
					mch[i][ch] |= 1 << (j - 1);
	
	dp[0][ns] = 1;
	for (int i = 0; i < len; ++i) {
		for (int s = 0; s <= ns; ++s) {
			if (dp[i][s] == -1) continue;
			for (int ch = 1; ch <= 26; ++ch) {
				int nxt = (s & mch[i + 1][ch]);
				if (dp[i + 1][nxt] == -1) dp[i + 1][nxt] = 0;
				dp[i + 1][nxt] = (dp[i + 1][nxt] + dp[i][s]) % mod;
			}
		}
	}
	
	int ans = 0;
	for (int s = 0; s <= ns; ++s) {
		int cntbit = 0;
		for (int i = 0; i < n; ++i)
			if (s & (1 << i)) ++cntbit;
		if (cntbit == m && dp[len][s] != -1)
			ans = (ans + dp[len][s]) % mod;
	}
	printf("%d\n", ans);
}
int main() {
	scanf("%d", &T);
	while (T--) solve();
	return 0;
}