学步园

Bill的挑战
问题描述：
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。

dp

用二进制表示匹配状态，枚举每位枚举字母进行对之前出现的状态进行转移

错误：模的数是1000003，打成了100003

program pset;
const
  maxn=1000003;
var
  ans,t,n,k,i,j,o,l,status,all,temp,q:longint;
  loop:char;
  s:array [0..15] of string[50];
  tot:array [0..1] of longint;
  f,dl:array [0..1,0..32768] of longint;
  yes:array [0..32768] of boolean;

function calc (temp:longint):longint;
var
  i,all:longint;
begin
  all:=0;
  for i:=1 to n do
    if (1 shl (i-1)) and temp <> 0 then inc(all);
  exit(all);
end;

begin
  assign(input,'set.in');
  reset(input);
  assign(output,'set.out');
  rewrite(output);
  readln(t);
  while t<>0 do
    begin
      readln(n,k);
      for i:=1 to n do
        readln(s[i]);
      l:=length(s[i]);
      o:=0;
      fillchar(f[o],sizeof(f[o]),0);
      f[o,(1 shl n) - 1]:=1;
      tot[o]:=1;
      dl[o,1]:=(1 shl n) - 1;
      for i:=1 to l do
        begin
          o:=1-o;
          fillchar(yes,sizeof(yes),false);
          fillchar(f[o],sizeof(f[o]),0);
          tot[o]:=0;
          for loop:='a' to 'z' do
            begin
              status:=0;
              all:=0;
              for j:=1 to n do
                if (s[j][i]=loop)or(s[j][i]='?') then
                  begin
                    inc(all);
                    status:=status+(1 shl (j-1));
                  end;
              if all<k then continue;
              for j:=1 to tot[1-o] do
                if f[1-o,dl[1-o,j]]<>0 then
                  begin
                    temp:=status and dl[1-o,j];
                    if calc(temp)<k then continue;
                    if not yes[temp] then
                      begin
                        yes[temp]:=true;
                        inc(tot[o]);
                        dl[o,tot[o]]:=temp;
                      end;
                    f[o,temp]:=(f[o,temp]+f[1-o,dl[1-o,j]]) mod maxn;
                  end;
            end;
        end;
      ans:=0;
      for i:=1 to tot[o] do
        if calc(dl[o,i])=k then ans:=(ans+f[o,dl[o,i]]) mod maxn;
      writeln(ans);
      dec(t);
    end;
  close(input);
  close(output);
end.