「SDOI2009」Bill的挑战
传送门
状压 ( ext{DP})
瞄一眼数据范围 (Nle15)，考虑状压。
设 (f[i][j]) 表示在所有串中匹配到第 (i) 位字符且匹配状态为 (j) 的方案数。
以及 (g[i][c]) 表示在所有串中匹配至第 (i) 位字符且第 (i) 位字符为 (c) 的合法最大匹配数（状态的数值最大）
那么我们就可以开始愉快地 ( ext{DP}) 啦。
参考代码：
/*--------------------------------
Code name: C.cpp
Author: The Ace Bee
This code is made by The Ace Bee
--------------------------------*/
#include <cstdio>
#include <cstring>
#define rg register
#define file(x)
freopen(x".in", "r", stdin);
freopen(x".out", "w", stdout);
inline int read() {
int s = 0; bool f = false; char c = getchar();
while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();
return f ? -s : s;
}
inline int count(int x) {
int res = 0;
while (x) res += x & 1, x >>= 1;
return res;
}
char s[17][55];
int f[55][1 << 15 | 10], g[55][30];
inline void plus(int& a, int b) { a = (a + b) % 1000003; }
int main() {
// file("C");
for (rg int T = read(); T; --T) {
memset(f, 0, sizeof f);
memset(g, 0, sizeof g);
int n = read(), k = read();
for (rg int i = 1; i <= n; ++i) scanf("%s", s[i]);
int len = strlen(s[1]);
for (rg int i = 0; i < len; ++i)
for (rg char c = 'a'; c <= 'z'; ++c)
for (rg int j = 1; j <= n; ++j)
if (s[j][i] == '?' || s[j][i] == c)
g[i][c - 'a'] |= 1 << (j - 1);
int lmt = (1 << n) - 1;
f[0][lmt] = 1;
for (rg int i = 0; i < len; ++i)
for (rg int j = 0; j <= lmt; ++j)
if (f[i][j])
for (rg char c = 'a'; c <= 'z'; ++c)
plus(f[i + 1][g[i][c - 'a'] & j], f[i][j]);
int ans = 0;
for (rg int i = 0; i <= lmt; ++i)
if (count(i) == k) plus(ans, f[len][i]);
printf("%d
", ans);
}
return 0;
}