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

· · 题解

这是一个非常无脑的，本菜鸡上文化课时自己想到的弱智状压，结果是对的只是非常慢，看没有人用这种写法于是我就决定发一篇qwq

非常无脑！

设f[i][j]表示有多少个串满足条件。

$i$表示现在匹配到了第$i$位 比如： $S1=a?,S2=ab,f[1][3(11)]=f[2][3(11)]=1,f[2][1(01)]=26

然后假设我们有了f[i][j],如何转移到f[i+1][???]\ \ ??????

我们先开一个数组hash[][]记录每一种字符出现的位置，把?字符转化成a~z

比如

S1=a S2=? S2=z

那么hash[\text{a}]={1,2}，1来源于S1，2来源于S2

hash[\text{b}]=hash[\text{c}]=...=hash[\text{y}]=${$2$}，$2$来源于$S2 hash[\text{z}]=${$2,3$}，$2$来源于$S2$,$3$来源于$S3

发现，如果我们枚举i+1位的字符ch，选择ch之后匹配的S串，就是hash[ch]!!!

然后我们就可以快乐的转移了~

设hash[ch]有size个数:

f[i+1][\sum_{i\le size}(1<<(has[ch][i]))]+=f[i][j]

代码如下:

#include<bits/stdc++.h>
#define ljc 1000003
using namespace std;
inline int getit(){
    //转化 a->1,b->2,...,z->26,?->27
    char ch=getchar();
    while (!isalpha(ch)&&(ch!='?')) ch=getchar();
    if (isalpha(ch)) return ch-'a'+1;
    else return 27;
}
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
    return x*f;
}
char s[10000];
int a[1600][5100],has[280][5100],len,T,n,m,f[51][33333];
inline int countbit(int x){
    //返回二进制数x中有多少为1
    int ans=0;
    while (x){
        if (x&1) ans++;
        x>>=1;
    }
    return ans;
}
int main(){
    T=read();
    while (T--){
        memset(f,-1,sizeof(f));
        memset(has,0,sizeof(has));
        n=read(),m=read();int ans=0;
        scanf("%s",s);len=strlen(s);
        for (int i=0;i<len;i++){
            if (isalpha(s[i])) a[1][i+1]=s[i]-'a'+1;
            else a[1][i+1]=27;
        }
        for (int i=2;i<=n;i++){
            for (int j=1;j<=len;j++){
                a[i][j]=getit();
            }
        }
        f[0][(1<<n)-1]=1;
        for (int i=0;i<len;i++){
            for (int P=0;P<(1<<n);P++){//P就是上述的j状态qwq
                if (f[i][P]==-1) continue;
                for (int k=1;k<=26;k++) has[k][0]=0;//has[i][0]表示上述的size qwq
                for (int j=1;j<=n;j++){
                    if ((P&(1<<j-1))==0) continue;
                    if (a[j][i+1]<=26) has[a[j][i+1]][++has[a[j][i+1]][0]]=j;
                    else{
                        for (int k=1;k<=26;k++) has[k][++has[k][0]]=j;
                    }   
                }
                for (int j=1;j<=26;j++){
                    if (has[j][0]){
                        int rev=0;
                        for (int k=1;k<=has[j][0];k++) rev+=(1<<has[j][k]-1);
                        if (f[i+1][rev]==-1) f[i+1][rev]=0;
                        f[i+1][rev]=(f[i+1][rev]+f[i][P])%ljc;//转移
                    }
                }
            }
        }
        for (int P=0;P<(1<<n);P++){
            if (f[len][P]==-1) continue;
            if (countbit(P)==m) ans=(ans+f[len][P])%ljc;
        }
        cout<<ans<<endl;
    }
    return 0;
}