Bill的挑战
Time Limit: 4 Sec Memory Limit: 64 MB[][][]Description
Input
第一行:一个整数T,表示数据的个数。
对于每组数据:
第一行:两个整数,N和K(含义如题目表述)。
接下来N行:每行一个字符串。
Output
T行,每行一个整数表示答案
Sample Input
1
2 1 a? ?bSample Output
50
HINT
T ≤ 5,M ≤ 15,字符串长度≤ 50。
Solution
我们运用状压DP,令 g[i][c] 表示第 i 位,用 字符c 来匹配可行的串的集合。
然后显然就可以DP啦!f[i][opt] 表示做到了第 i 位,匹配集合为opt的方案数。
Code
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 using namespace std; 10 typedef long long s64;11 12 const int ONE = 4e5 + 5;13 const int MOD = 1000003;14 15 int n, m, T;16 int g[52][52], f[52][32769];17 char s[25][52];18 int Ans;19 20 int get()21 {22 int res=1,Q=1;char c;23 while( (c=getchar())<48 || c>57 ) 24 if(c=='-')Q=-1; 25 res=c-48; 26 while( (c=getchar())>=48 && c<=57 )27 res=res*10+c-48; 28 return res*Q;29 }30 31 32 void Deal()33 {34 memset(g, 0, sizeof(g));35 memset(f, 0, sizeof(f));36 n = get(); m = get();37 for(int i = 1; i <= n; i++)38 scanf("%s", s[i] + 1);39 40 int len = strlen(s[1] + 1);41 for(int i = 1; i <= len; i++)42 for(int c = 1; c <= 26; c++)43 for(int j = 1; j <= n; j++)44 if(s[j][i] == '?' || s[j][i] == c + 'a' - 1)45 g[i][c] |= 1 << j - 1;46 47 int total = (1 << n) - 1;48 f[1][total] = 1;49 for(int i = 1; i <= len; i++)50 for(int opt = 0; opt <= total; opt++)51 if(f[i][opt])52 for(int c = 1; c <= 26; c++)53 (f[i + 1][opt & g[i][c]] += f[i][opt]) %= MOD;54 55 Ans = 0;56 for(int opt = 0; opt <= total; opt++)57 {58 int num = 0;59 for(int j = 1; j <= n; j++)60 if(opt & (1 << j - 1)) num++;61 if(num == m) Ans = (Ans + f[len + 1][opt]) % MOD;62 }63 64 printf("%d\n", Ans);65 }66 67 int main()68 {69 T = get();70 while(T--)71 Deal();72 }73