bzoj 1879: [Sdoi2009]Bill的挑战

题目链接

bzoj 1879: [Sdoi2009]Bill的挑战

题解

n<=15,装压吧

对所有字符串进行装压

可以预处理一个数组can[i][j]表示所有的字符串中,有哪些可以在第i位匹配桑z

然后dp[i][j]表示T串第i位上取字符所对的状态j的方案

代码

#include<vector>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define mod 1000003

using std::max;

using std::min;

inline int read() {

    int x=0,f=1;

    char c=getchar();

    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar() ;}

    while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar() ;

    return x*f;

}

int T,n,k;

char a[17][57];

int dp[57][1<<17];

int can[57][39];

void work() {

    memset(dp,0,sizeof dp);

    memset(can,0,sizeof can);

    int po=(1<<n)-1;

    int len=strlen(a[1]);

//	printf("%d %c\n",len,a[1][1]);

    for(int i=0;i<len;++i)

        for(char j='a';j<='z';++j)

            for(int k=1;k<=n;++k)

                if(a[k][i]=='?'||a[k][i]==j)

                    can[i][j-'a']|=(1<<k-1);

    dp[0][po]=1;

    for(int i=0;i<len;++i)

        for(int j=0;j<=po;++j) {

            if(dp[i][j])

                for(char k='a'-'a';k<='z'-'a';++k)

                    dp[i+1][can[i][k]&j]=(dp[i+1][can[i][k]&j]+dp[i][j])%mod;

        }

    int ans=0;

    for(int cnt,i=0;i<=po;++i) {

        cnt=0;

        for(int j=1;j<=po;j<<=1) cnt+=(i&j) ? 1:0;

        if(cnt==k) ans=(ans+dp[len][i])%mod;

    }

    printf("%d\n",ans);

    return;

}

int main()  {

    T=read();

    for(;T--;) {

        n=read(),k=read();

        for(int i=1;i<=n;++i)  scanf("%s",a[i]);

        work();

    }

    return 0;

}