JSOI2007文本生成器

2023-08-26 16:19:22

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

代码：

 const p=;

 var a:array[..,..] of longint;

     fail,q:array[..] of longint;

     f:array[..,..] of longint;

     s:string;

     flag:array[..] of boolean;

     i,j,n,m,ans1,ans2,tot,h,t:longint;

 procedure insert;

  var i,j,now:longint;

  begin

  readln(s);now:=;

  for i:= to length(s) do

   begin

   j:=ord(s[i])-ord('A')+;

   if a[now,j]= then begin inc(tot);a[now,j]:=tot;end;

   now:=a[now,j];

   end;

   flag[now]:=true;

  end;

 procedure acmatch;

  var i,now,k:longint;

  begin

  h:=;t:=;q[]:=;fail[]:=;

  while h<t do

   begin

   inc(h);now:=q[h];

   for i:= to  do

    begin

    if a[now,i]= then continue;

    k:=fail[now];

    while a[k,i]= do k:=fail[k];

    fail[a[now,i]]:=a[k,i];

    if flag[a[k,i]] then flag[a[now,i]]:=true;

    inc(t);q[t]:=a[now,i];

    end;

   end;

  end;

 procedure init;

  begin

  tot:=;

  readln(n,m);

  for i:= to  do a[,i]:=;

  for i:= to n do insert;

  acmatch;

  end;

 procedure dp(x:longint);

  var i,j,k:longint;

  begin

  for i:= to tot do

   begin

   if (flag[i]) or (f[x-,i]=) then continue;

   for j:= to  do

    begin

     k:=i;

     while a[k,j]= do k:=fail[k];

     f[x,a[k,j]]:=(f[x,a[k,j]]+f[x-,i]) mod p;

    end;

   end;

  end;

 procedure main;

  begin

  f[,]:=;

  for i:= to m do dp(i);

  ans2:=;ans1:=;

  for i:= to m do ans2:=(ans2*) mod p;

  for i:= to tot do writeln(f[m,i]);

  for i:= to tot do

   if not(flag[i]) then ans1:=(ans1+f[m,i]) mod p;

  writeln((ans2-ans1+p) mod p);

  end;

 begin

  assign(input,'input.txt');assign(output,'output.txt');

  reset(input);rewrite(output);

  init;

  main;

  close(input);close(output);

 end.

AC自动机模版！

码农公寓