首页 题解

# Description

Luogu传送门

# Solution

观察到数据范围：状压就你了！

于是我们快乐地使用状压 dpdp来解决这个问题。

首先我们开一个 match[i][j]match[i][j] 数组表示所有字符串第 ii 位能否匹配 j∈a⋅⋅⋅zj \in a···z（这个描述起来有点抽象，可以根据代码理解一下）。

然后就是 dpdp 了，我们设 dp[i][k]dp[i][k] 表示第 ii 位匹配 k(k∈a⋅⋅⋅z)k(k \in a···z) 的方案数。

转移方程：

dp[i+1][match[i][k]&j]+=dp[i][j]dp[i + 1][match[i][k] \& j] += dp[i][j]

最后再按位枚举，统计答案即可。

# Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

using namespace std;

const int N = 55;
const int p = 1e6 + 3;
int T, n, m;
int dp[N][1 << 15], match[N][N];
char s[N][N];

int main(){
    scanf("%d", &T);
    while(T--){
        memset(dp, 0, sizeof(dp));
        memset(match, 0, sizeof(match));
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i) scanf("%s", s[i]);
        int len = strlen(s[1]);
        for(int i = 0; i < len; ++i)
            for(int j = 0; j < 26; ++j)
                for(int k = 1; k <= n; ++k)
                    if(s[k][i] == '?' || s[k][i] - 'a' == j)
                        match[i][j] |= (1 << (k - 1)); 
        int sta = (1 << n) - 1;
        dp[0][sta] = 1;
        for(int i = 0; i < len; ++i)
            for(int j = 0; j <= sta; ++j)
                if(dp[i][j])
                    for(int k = 0; k < 26; ++k)
                        dp[i + 1][match[i][k] & j] = (dp[i + 1][match[i][k] & j] + dp[i][j]) % p;
        int ans = 0;
        for(int i = 0, res = 0; i <= sta; ++i, res = 0){
            for(int j = 1; j <= sta; j <<= 1) res += (bool)(i & j);
            if(res == m) ans = (ans + dp[len][i]) % p;
        }
        printf("%d\n", ans);
    }
    return 0;
}

# End