JSOI2007文本生成器

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

1030: [JSOI2007]文本生成器

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 1613 Solved: 656
[Submit][Status]

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

HINT

代码：

 1 const p=10007;
 2 var a:array[0..6001,0..27] of longint;
 3     fail,q:array[0..6001] of longint;
 4     f:array[0..101,0..6001] of longint;
 5     s:string;
 6     flag:array[0..6001] of boolean;
 7     i,j,n,m,ans1,ans2,tot,h,t:longint;
 8 procedure insert;
 9  var i,j,now:longint;
10  begin
11  readln(s);now:=1;
12  for i:=1 to length(s) do
13   begin
14   j:=ord(s[i])-ord(‘A‘)+1;
15   if a[now,j]=0 then begin inc(tot);a[now,j]:=tot;end;
16   now:=a[now,j];
17   end;
18   flag[now]:=true;
19  end;
20 procedure acmatch;
21  var i,now,k:longint;
22  begin
23  h:=0;t:=1;q[1]:=1;fail[1]:=0;
24  while h<t do
25   begin
26   inc(h);now:=q[h];
27   for i:=1 to 26 do
28    begin
29    if a[now,i]=0 then continue;
30    k:=fail[now];
31    while a[k,i]=0 do k:=fail[k];
32    fail[a[now,i]]:=a[k,i];
33    if flag[a[k,i]] then flag[a[now,i]]:=true;
34    inc(t);q[t]:=a[now,i];
35    end;
36   end;
37  end;
38 procedure init;
39  begin
40  tot:=1;
41  readln(n,m);
42  for i:=1 to 26 do a[0,i]:=1;
43  for i:=1 to n do insert;
44  acmatch;
45  end;
46 procedure dp(x:longint);
47  var i,j,k:longint;
48  begin
49  for i:=1 to tot do
50   begin
51   if (flag[i]) or (f[x-1,i]=0) then continue;
52   for j:=1 to 26 do
53    begin
54     k:=i;
55     while a[k,j]=0 do k:=fail[k];
56     f[x,a[k,j]]:=(f[x,a[k,j]]+f[x-1,i]) mod p;
57    end;
58   end;
59  end;
60 procedure main;
61  begin
62  f[0,1]:=1;
63  for i:=1 to m do dp(i);
64  ans2:=1;ans1:=0;
65  for i:=1 to m do ans2:=(ans2*26) mod p;
66  for i:=1 to tot do writeln(f[m,i]);
67  for i:=1 to tot do
68   if not(flag[i]) then ans1:=(ans1+f[m,i]) mod p;
69  writeln((ans2-ans1+p) mod p);
70  end;
71 begin
72  assign(input,‘input.txt‘);assign(output,‘output.txt‘);
73  reset(input);rewrite(output);
74  init;
75  main;
76  close(input);close(output);
77 end.
78