1030: [JSOI2007]文本生成器 - BZOJ

浏览数：15 / 时间：2015年06月09日

Description

JSOI交给队员ZYX一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章—— 也就是说，生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章a包含单词b，当且仅当单词b是文章a的子串）。但是，即使按照这样的标准，使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。 ZYX需要指出GW文本生成器 v6生成的所有文本中可读文本的数量，以便能够成功获得v7更新版。你能帮助他吗？
Input

输入文件的第一行包含两个正整数，分别是使用者了解的单词总数N (<= 60)，GW文本生成器 v6生成的文本固定长度M；以下N行，每一行包含一个使用者了解的单词。这里所有单词及文本的长度不会超过100，并且只可能包含英文大写字母A..Z　。
Output

一个整数，表示可能的文章总数。只需要知道结果模10007的值。
Sample Input
2 2
A
B

Sample Output
100

在AC自动机上的dp

f[i,j,k]表示长度为i，在节点j，状态为k的方案数（k=0时为不匹配，k=1时为匹配）

  1 const
  2     maxn=6010;
  3     maxm=105;
  4     h=10007;
  5 type
  6     node=record
  7       fail:integer;
  8       flag:boolean;
  9       go:array[‘A‘..‘Z‘]of integer;
 10     end;
 11 var
 12     tree:array[0..maxn]of node;
 13     f:array[0..maxn,0..maxn,0..1]of integer;
 14     n,m,tot:longint;
 15     s:string;
 16 
 17 procedure insert;
 18 var
 19     i,j:longint;
 20 begin
 21     readln(s);
 22     j:=0;
 23     for i:=1 to length(s) do
 24       begin
 25         if tree[j].go[s[i]]=0 then
 26         begin
 27           inc(tot);
 28           tree[j].go[s[i]]:=tot;
 29         end;
 30         j:=tree[j].go[s[i]];
 31       end;
 32     tree[j].flag:=true;
 33 end;
 34 
 35 var
 36     q:array[0..maxn]of longint;
 37     head,tail:longint;
 38 
 39 procedure build;
 40 var
 41     i:char;
 42     k:longint;
 43 begin
 44     head:=1;
 45     tail:=1;
 46     q[1]:=0;
 47     while head<=tail do
 48       begin
 49         for i:=‘A‘ to ‘Z‘ do
 50           if tree[q[head]].go[i]<>0 then
 51           begin
 52             inc(tail);
 53             q[tail]:=tree[q[head]].go[i];
 54             k:=tree[q[head]].fail;
 55             if k<>q[head] then
 56             begin
 57               while (k<>0) and (tree[k].go[i]=0) do
 58                 k:=tree[k].fail;
 59               tree[q[tail]].fail:=tree[k].go[i];
 60             end;
 61           end;
 62         for i:=‘A‘ to ‘Z‘ do
 63           if tree[q[head]].go[i]=0 then tree[q[head]].go[i]:=tree[tree[q[head]].fail].go[i];
 64         if tree[tree[q[head]].fail].flag then tree[q[head]].flag:=true;
 65         inc(head);
 66       end;
 67 end;
 68 
 69 procedure init;
 70 var
 71     i:longint;
 72 begin
 73     readln(n,m);
 74     for i:=1 to n do
 75       insert;
 76     build;
 77 end;
 78 
 79 procedure work;
 80 var
 81     i,j,ans:longint;
 82     s:char;
 83 begin
 84     for s:=‘A‘ to ‘Z‘ do
 85       if tree[tree[0].go[s]].flag then inc(f[1,tree[0].go[s],1])
 86       else inc(f[1,tree[0].go[s],0]);
 87     for i:=1 to m-1 do
 88       for j:=0 to tot do
 89         for s:=‘A‘ to ‘Z‘ do
 90           if tree[tree[j].go[s]].flag then f[i+1,tree[j].go[s],1]:=(f[i+1,tree[j].go[s],1]+f[i,j,0]+f[i,j,1])mod h
 91           else
 92             begin
 93               f[i+1,tree[j].go[s],1]:=(f[i+1,tree[j].go[s],1]+f[i,j,1])mod h;
 94               f[i+1,tree[j].go[s],0]:=(f[i+1,tree[j].go[s],0]+f[i,j,0])mod h;
 95             end;
 96     ans:=0;
 97     for i:=0 to tot do
 98       ans:=(ans+f[m,i,1])mod h;
 99     writeln(ans);
100 end;
101 
102 begin
103     init;
104     work;
105 end.