记录编号	414650	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] Bill的挑战	最终得分	100
用户昵称	BaDBoY	是否通过	通过
代码语言	C++	运行时间	0.150 s
提交时间	2017-06-14 17:55:55	内存使用	3.41 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline int read(){
  int s=0,f=1; char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')f=-1; ch=getchar();}
  while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
  return s*f;
}
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]) 
     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 llll;
int pp(){
 freopen("set.in","r",stdin);
   freopen("set.out","w",stdout);
   t=read();
   while(t--){
     n=read(),k=read();
     clear();
     for(int i=1;i<=n;i++)  getread(i);
     work();
   }
   //while(1);
   return 0;
}
int ll=pp();
int main(){
  ;
}