Bill的挑战

Time Limit: 4 Sec Memory Limit: 64 MB

Description

img

Input

第一行：一个整数T，表示数据的个数。

对于每组数据：

第一行：两个整数，N和K（含义如题目表述）。

接下来N行：每行一个字符串。

Output

T行，每行一个整数表示答案

Sample Input

1
　　2 1
　　a?
　　?b

Sample Output

50

HINT

T ≤ 5，M ≤ 15，字符串长度≤ 50。

Solution

我们运用状压DP，令 g[i][c] 表示第 i 位，用 字符c 来匹配可行的串的集合。

然后显然就可以DP啦！f[i][opt] 表示做到了第 i 位，匹配集合为opt的方案数。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 4e5 + 5;
const int MOD = 1000003;

int n, m, T;
int g[52][52], f[52][32769];
char s[25][52];
int Ans;

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}


void Deal()
{
    memset(g, 0, sizeof(g));
    memset(f, 0, sizeof(f));
    n = get();  m = get();
    for(int i = 1; i <= n; i++)
        scanf("%s", s[i] + 1);

    int len = strlen(s[1] + 1);
    for(int i = 1; i <= len; i++)
        for(int c = 1; c <= 26; c++)
            for(int j = 1; j <= n; j++)
                if(s[j][i] == '?' || s[j][i] == c + 'a' - 1)
                    g[i][c] |= 1 << j - 1;

    int total = (1 << n) - 1;
    f[1][total] = 1;
    for(int i = 1; i <= len; i++)
        for(int opt = 0; opt <= total; opt++)
            if(f[i][opt])
                for(int c = 1; c <= 26; c++)
                    (f[i + 1][opt & g[i][c]] += f[i][opt]) %= MOD;

    Ans = 0;
    for(int opt = 0; opt <= total; opt++)
    {
        int num = 0;
        for(int j = 1; j <= n; j++)
            if(opt & (1 << j - 1)) num++;
        if(num == m) Ans = (Ans + f[len + 1][opt]) % MOD;
    }

    printf("%d\n", Ans);
}

int main()
{
    T = get();
    while(T--)
        Deal();
}