「SDOI2009」Bill的挑战

「SDOI2009」Bill的挑战

传送门
状压 \(\text{DP}\)
瞄一眼数据范围 \(N\le15\)，考虑状压。
设 \(f[i][j]\) 表示在所有串中匹配到第 \(i\) 位字符且匹配状态为 \(j\) 的方案数。
以及 \(g[i][c]\) 表示在所有串中匹配至第 \(i\) 位字符且第 \(i\) 位字符为 \(c\) 的合法最大匹配数（状态的数值最大）
那么我们就可以开始愉快地 \(\text{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\n", ans);
    }
    return 0;
}

「SDOI2009」Bill的挑战

原文：https://www.cnblogs.com/zsbzsb/p/12246850.html