Bill的挑战

422. Bill的挑战

★★☆   输入文件： set.in   输出文件： set.out    简单对比
时间限制：1 s   内存限制：256 MB

问题描述：
Sheng bill不仅有惊人的心算能力，还可以轻松地完成各种统计。在昨天的比赛中，你凭借
优秀的程序与他打成了平局，这导致Sheng bill极度的不满。于是他再次挑战你。这次你可不
能输！
这次，比赛规则是这样的：
给N个长度相同的字符串（由小写英文字母和′
?′
组成），S1, S2, . . . , SN，求与这N个串中
的刚好K个串匹配的字符串T的个数（答案模1000003）。
若字符串Sx（1 ≤ x ≤ N）和T匹配，满足以下条件：
1. Sx.length = T.length。
2. 对于任意的1 ≤ i ≤ Sx.length，满足Sx[i] =′
?′
或者Sx[i] = T[i]。
其中T只包含小写英文字母。
输入格式：
本题包含多组数据。
第一行：一个整数T，表示数据的个数。
对于每组数据：
第一行：两个整数，N和K（含义如题目表述）。
接下来N行：每行一个字符串。
输出格式：
对于每组数据，输出方案数目（共T行）。
样例输入：
1
2 1
a?
?b
样例输出：
50
数据范围：
对于30%的数据，T ≤ 5，N ≤ 5，字符串长度≤ 20；
对于70%的数据，T ≤ 5，N ≤ 13，字符串长度≤ 30；
对于100%的数据，T ≤ 5，N ≤ 15，字符串长度≤ 50。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int mod=1e6+3;
const int mxn=100010;
int f[51][1<<15];
int g[51][27];
char s[16][52];
int T,n,K;
int main(){
      freopen("set.in","r",stdin);freopen("set.out","w",stdout);
     int i,j;
    scanf("%d",&T);
    while(T--){
        memset(f,0,sizeof f);
        scanf("%d%d",&n,&K);
        for(i=0;i<n;i++){scanf("%s",s[i]);}
        int len=strlen(s[0]);
        for(i=0;i<len;i++)
            for(int k=0;k<26;k++){     
                g[i][k]=0;
                for(j=0;j<n;j++){
                    if(s[j][i]=='?' || s[j][i]==k+'a')g[i][k]|=(1<<j);
                }
            }
        int ed=(1<<n)-1;
        f[0][ed]=1;
        for(i=1;i<=len;i++){
            for(int k=0;k<=ed;k++){
                if(f[i-1][k])
                for(j=0;j<26;j++){
                    (f[i][k&g[i-1][j]]+=f[i-1][k])%=mod;
                }
            }
        }
        int ans=0;
        for(int k=0;k<=ed;k++){
            int tmp=k,cnt=0;
            while(tmp){
                cnt++;
                tmp-=tmp&-tmp;
            }
            if(cnt==K)ans=(ans+f[len][k])%mod;
        }
        printf("%d\n",ans);
    }
    return 0;
}