记录编号	407380	评测结果	AAAAAAAAAA
题目名称	422.[SDOI 2009] Bill的挑战	最终得分	100
用户昵称	BaDBoY	是否通过	通过
代码语言	C++	运行时间	0.233 s
提交时间	2017-05-21 16:03:00	内存使用	6.82 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t,n,k,len,tot;
char s[16][51];
int f[52][1<<15|1],temp[51][30];
inline void clear(){
  memset(s,0,sizeof(s));
  memset(temp,0,sizeof(temp));
  memset(f,0,sizeof(f));
  len=0;
}
inline void getread(int x){
   len=0;
   char ch=getchar();
   while((ch>'z'||ch<'a')&&ch!='?') ch=getchar();
   while(ch=='?'||(ch>='a'&&ch<='z')){
     s[x][++len]=ch; ch=getchar();
   }
   return ;
}
inline int low(int x){
  return x&(-x);
}
inline int sum(int x){
  int num=0;
  while(x){
    num++;
    x-=low(x);
  }
  return num;
}
inline void work(){
  for(int i=1;i<=len;i++)
   for(char k='a';k<='z';k++)
    for(int j=1;j<=n;j++)
     if(s[j][i]=='?'||s[j][i]==k)
      temp[i][k-'a']|=(1<<(j-1));  //这一位是这个字母时可以处理几个串 
  f[1][(1<<n)-1]=1;//到第一位全匹配有一个???? 
  for(int i=1;i<=len;i++)
   for(int j=0;j<(1<<n);j++)
    if(!f[i][j]) continue;//不能转移 
    else 
     for(char k='a';k<='z';k++){
      f[i+1][j&temp[i][k-'a']]+=f[i][j];
      f[i+1][j&temp[i][k-'a']]%=1000003; 
     } 
  int ans=0;
  for(int i=0;i<(1<<n);i++)
   if(f[len+1][i]&&sum(i)==k){
    ans+=f[len+1][i];
    ans%=1000003;
   }
  printf("%d\n",ans);
}
int main(){
   freopen("set.in","r",stdin);
   freopen("set.out","w",stdout);
   scanf("%d",&t);
   while(t--){
     scanf("%d%d",&n,&k);
     clear();
     for(int i=1;i<=n;i++)  getread(i);
     work();
   }
   //while(1);
   return 0;
}