879: [Sdoi2009]Bill的挑战

Time Limit: 4 Sec  Memory Limit: 64 MB

Submit: 852  Solved: 435

[][][]

Description

Input

本题包含多组数据。 

第一行：一个整数T，表示数据的个数。 

对于每组数据： 

第一行：两个整数，N和K（含义如题目表述）。 

接下来N行：每行一个字符串。

T ≤ 5，M ≤ 15，字符串长度≤ 50。

Output

如题

Sample Input

5

3 3

???r???

???????

???????

3 4

???????

?????a?

???????

3 3

???????

?a??j??

????aa?

3 2

a??????

???????

???????

3 2

???????

???a???

????a??

Sample Output

914852

0

0

871234

67018

HINT 

Source

 代码：

//这题真难啊//n只有15可以知道用状压dp，给出的n个字符串一样长，dp[i][j]表示到i位置时有j状态满足到前i位为止和T串不同的方案数，//可以这样转移：dp[i][p&q]+=dp[i-1][p],而且转移时不仅要枚举位置i和状态j还要枚举'a'~'z'的字符k，表示当i位取k时的状态j//是由i-1位时状态p转移而来。这里的 p&q 就是i-1到i位置且i位置取k字符时后的状态。可以先用g[i][j]表示i位置是j字符的状态//有哪些(二进制压缩)，处理出来。#include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;const int mod=1e6+3;char str[20][60];int dp[60][1<<16],g[60][30];int main(){    int t,n,m;    scanf("%d",&t);    while(t--){        scanf("%d%d",&n,&m);        for(int i=0;i
         
          >=1;            }            if(cnt==m) ans=(ans+dp[len][i])%mod;        }        printf("%d\n",ans);    }    return 0;}