洛谷2167 [SDOI2009]Bill的挑战

题意

有 $N$ 个长度相同的字符串，问恰好与其中 $K$ 个匹配的字符串有多少个。

定义满足如下条件的字符串 $x$ 和 $y$ 为匹配的：

1. $len_x=len_y$
2. $\forall 1\le i\le len_x \ , \ x[i]='?' \ or \ x[i]=y[i]$

其中 $N\le 15$ ，字符串长度 $len\le 50$ 。

题解

看数据范围，可以对 $N$ 进行状压。

先预处理一个数组 $can[i][j]$ ，表示所有字符串中第 $i$ 位能与字符 $j$ 匹配的二进制情况。

然后对每一位枚举匹配状态进行dp。用 $f[i][j]$ 表示第 $i$ 位状态为 $j$ 能匹配的字符串的个数，转移方程式即为：

$$f[i+1][j\& can[i][k]]+=f[i][j]$$

其中 $k$ 为枚举的字符。

最后统计 $1$ 的个数为 $K$ 的状态的答案即可。

#include<bits/stdc++.h>
#define ha 1000003

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

char s[20][55];
int can[55][26],f[55][32768],ok[10005],cnt,t,n,m,N;

inline void init()
{
    memset(f,0,sizeof(f));
    memset(can,0,sizeof(can));
}

inline int get_1(int x)
{
    int ans=0;
    while (x) x&=x-1,ans++;
    return ans;
}

int main()
{
    t=read();
    while (t--)
    {
        init();
        n=read(); m=read(); N=1<<n;
        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 j=0;j<26;j++)
            {
                for (int k=1;k<=n;k++)
                {
                    if (s[k][i]!='?' && s[k][i]-'a'!=j) continue;
                    can[i][j]|=1<<(k-1);
                }
            }
        }
        f[1][N-1]=1;
        for (int i=1;i<=len;i++)
        {
            for (int j=0;j<N;j++)
            {
                if (!f[i][j]) continue;
                for (int k=0;k<26;k++) f[i+1][can[i][k]&j]=(f[i+1][can[i][k]&j]+f[i][j])%ha;
            }
        }
        int ans=0;
        for (int i=0;i<N;i++)
        {
            if (get_1(i)!=m) continue;
            ans=(ans+f[len+1][i])%ha;
        }
        printf("%d\n",ans);
    }
    return 0;
}