Bill的挑战(set)

孙和安
2023-12-01
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.


 类似资料: