题目链接
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;
}
转载于:https://www.cnblogs.com/sssy/p/8471378.html
