Bzoj1879 [Sdoi2009]Bill的挑战

Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 724 Solved: 363

Description

Input

本题包含多组数据。第一行：一个整数T，表示数据的个数。对于每组数据：第一行：两个整数，N和K（含义如题目表述）。接下来N行：每行一个字符串。

Output

2 1

Sample Input

Sample Output

对于30%的数据，T ≤ 5，N ≤ 5，字符串长度≤ 20；
对于70%的数据，T ≤ 5，N ≤ 13，字符串长度≤ 30；
对于100%的数据，T ≤ 5，N ≤ 15，字符串长度≤ 50。

HINT

Source

Day2

动规状压DP

这题简直思路清奇。

刚开始想的是预处理出每两个串之间能否匹配，以及每个串能匹配它之前出现的多少串，然后DP。←想来好复杂，而且可能还要容斥，那就是超复杂了。

　　（说不定也能强行做出来呢 http://www.cnblogs.com/SilverNebula/p/6001294.html）

再一看数据范围，啊，状压你好。

所有串的长度一样，所以可以统一处理，预处理g[i][j]=x表示字符j可以和x集合内的串的第i位匹配

f[匹配长度][集合]=方案数

f[0][全满集合]=1

f[i][ k&g[i-1][j] ]+=f[递推位数i-1][枚举集合k]

 /*by SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<vector>

 using namespace std;

 const int mod=1e6+;

 const int mxn=;

 int f[][<<];

 int g[][];

 char s[][];

 int T,n,K;

 int main(){

     int i,j;

     scanf("%d",&T);

     while(T--){

         memset(f,,sizeof f);

         scanf("%d%d",&n,&K);

         for(i=;i<n;i++){scanf("%s",s[i]);}

         int len=strlen(s[]);

         for(i=;i<len;i++)//长度

             for(int k=;k<;k++){//字母

                 g[i][k]=;

                 for(j=;j<n;j++){//串

                     if(s[j][i]=='?' || s[j][i]==k+'a')g[i][k]|=(<<j);

                 }

             }

         int ed=(<<n)-;

         f[][ed]=;

         for(i=;i<=len;i++){

             for(int k=;k<=ed;k++){

                 if(f[i-][k])

                 for(j=;j<;j++){

                     (f[i][k&g[i-][j]]+=f[i-][k])%=mod;

                 }

             }

         }

         int ans=;

         for(int k=;k<=ed;k++){

             int tmp=k,cnt=;

             while(tmp){

                 cnt++;

                 tmp-=tmp&-tmp;

             }

             if(cnt==K)ans=(ans+f[len][k])%mod;

         }

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

     }

     return ;

 }

巴特西