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

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;
LL t,n,b,m;
LL g[60][50],f[60][1<<16];
LL d=1000003;
string a[30];
void init()
{
     for(int i=0;i<m;i++)
       for(int j='a';j<='z';j++)
          for(int k=1;k<=n;k++)
          {
                  if(a[k][i]==j||a[k][i]=='?')
                       g[i][j-'a']|=(1<<(k-1));
          }     
     /*for(int i=1;i<=m;i++){
        for(int j=0;j<(1<<n);j++)
            cout<<f[i][j]<<" ";
        cout<<endl;   
     }*/
}
void dp()
{
     f[0][(1<<(n))-1]=1;
     for(int i=0;i<m;i++)
        for(int k=0;k<(1<<n);k++)
           if(f[i][k])
           {
                for(int j='a';j<='z';j++)
                {
                     f[i+1][k&g[i][j-'a']]+=f[i][k]%d;                    
                } 
           }
     
}
int main()
{
    freopen("set.in","r",stdin);
    freopen("set.out","w",stdout);
    cin>>t;
    while(t--)
    {
         memset(f,0,sizeof(f));
         memset(g,0,sizeof(g));
         scanf("%lld%lld",&n,&b);
         for(int i=1;i<=n;i++)
            cin>>a[i];
         m=a[1].size();
         init();     
         dp();
         LL s=0;
         for(int i=0;i<(1<<n);i++)
         {
              int tot=0;
              for(int j=0;j<n;j++)
                 if(i&(1<<j))
                     tot++;
              if(tot==b)
                 s+=f[m][i]%d; 
         }
         printf("%lld\n",s%d);
    }
    //while(1);
}