自动搬运

查看原文

来自洛谷，原作者为

	远航之曲 **

搬运于2025-08-24 21:34:42，当前版本为作者最后更新于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);
    }
}