题解 P2167 【[SDOI2009]Bill的挑战】

远航之曲 · 2017-04-16 08:41:07 · 题解

安利一下博客

一眼数据范围：你好状压

因为每个字符串都是相同长度的，我们可以先预处理一个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);
    }
}