luogu 2167 [SDOI2009]Bill的挑战

还是一道诡异的DP

地址：luogu2167

题目描述

输入输出格式

输入格式：

本题包含多组数据。 第一行：一个整数T，表示数据的个数。 对于每组数据： 第一行：两个整数，N和K（含义如题目表述）。 接下来N行：每行一个字符串。

输出格式：

T行整数，表示结果

输入输出样例

输入样例#1：

1
2 1
a?
?b

输出样例#1：

50

数据范围

对于30%的数据，T ≤ 5，M ≤ 5，字符串长度≤ 20；

对于70%的数据，T ≤ 5，M ≤ 13，字符串长度≤ 30；

对于100%的数据，T ≤ 5，M ≤ 15，字符串长度≤ 50。

题解

一眼数据范围：你好状压

因为每个字符串都是相同长度的，我们可以先预处理一个$match[1 \cdots len][a \cdots z]$，里面用二进制表示￥1 \cdots n￥位的字符串的第￥i￥位是否可以匹配上￥a \cdots z￥。

然后转移就非常好想了，￥f[i][j]￥表示第i位的匹配上了j这个状态的方案数，然后随便瞎搞统计结果就行了。。。

#include <cstdio>
#include <cstring>
using namespace std;
char s[100][100];
int f[55][1<<15];
int n,k,len,tot,mod=1000003;
int match[50][50];
void check(int x,int y)
{
    for (int i=0;i<=len;i++)
        if (!(s[x][i]=='?'||s[y][i]=='?'||s[x][i]==s[y][i]))
            return;
    match[x][y]=match[y][x]=1;
}
main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(f,0,sizeof f);
        memset(match,0,sizeof match);
        tot=0;
        scanf("%d%d",&n,&k);
        for (int i=1;i<=n;i++)
            scanf("%s",s[i]);
        len=strlen(s[1]);

        for (int i=0;i<len;i++)
            for (char ch='a';ch<='z';ch++)
                for (int j=1;j<=n;j++)
                    if (s[j][i]=='?'||s[j][i]==ch)
                        match[i][ch-'a']|=(1<<j-1);
        int cnt=(1<<n)-1;
        f[0][cnt]=1;
        for (int i=0;i<len;i++)
            for (int j=0;j<=cnt;j++)
                if (f[i][j])
                    for (char ch='a';ch<='z';ch++)
                        f[i+1][match[i][ch-'a']&j]+=f[i][j],
                        f[i+1][match[i][ch-'a']&j]%=mod;
        for (int i=0;i<=cnt;i++)
        {
            int ans=0;
            for (int j=1;j<=cnt;j<<=1) ans+=(bool)(i&j);
            if (ans==k) tot=(tot+f[len][i])%mod;
        }
        printf("%d\n",tot);
    }
}