必赢亚洲手机app下载


有关电脑软件不可以正常联网的缓解方法

翻译:电脑软件wiki中的business logic词条

文本生成器

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

 

 

思路

先是次打AC自动机的题材,酷爱动啊。

第一那题需求长度为m的盈盈给定串中最少一个的字符串的个数。

那么不妨求它的反面,即长度为m的不分包自由一个给定串的字符串个数。

考虑dp+ac自动机。

一个尺寸为m的知足条件的字符串,

约等于从根节点开头,在AC自动机上走m步,且未经过非法节点(有给定串在此时此刻节点为止)。

f[i][j]意味着字符串前i位已规定,当前走到j号点,的方案数。

ok了。

 

代码

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 #define ref(i,x,y)for(int i=x;i<=y;++i)
 6 const int N=6010;
 7 const int mod=10007;
 8 int n,m,ans,q[N],dp[101][N],tot=1;
 9 char s[101];
10 struct node{
11     bool ok;
12     int fail,ch[26];
13 }a[N];
14 int mi(int a,int b)
15 {
16     int res=1;
17     ref(i,1,b)res=res*a%mod;
18     return res;
19 }
20 void insert()
21 {
22     int len=strlen(s),now=1;
23     ref(i,0,len-1)
24     {
25         int &t=a[now].ch[s[i]-'A'];
26         if(!t)t=++tot; now=t;
27     }
28     a[now].ok=1;
29 }
30 void getfail()
31 {
32     ref(i,0,25)a[0].ch[i]=1;
33     q[1]=1;a[1].fail=0;
34     for(int h=1,t=1,x=q[h];h<=t;++h,x=q[h])
35     ref(i,0,25)
36     {
37         if(!a[x].ch[i])continue;
38         int p=a[x].fail,s=q[++t]=a[x].ch[i];
39         while(!a[p].ch[i])p=a[p].fail;
40         a[s].fail=a[p].ch[i];
41         if(a[a[p].ch[i]].ok)a[s].ok=1;
42     }
43 }
44 void work()
45 {
46     dp[0][1]=1;
47     ref(i,1,m)ref(j,1,tot)if(!a[j].ok&&dp[i-1][j])
48     ref(k,0,25)
49     {
50         int p=j;
51         while(!a[p].ch[k])p=a[p].fail;
52         (dp[i][a[p].ch[k]]+=dp[i-1][j])%=mod;
53     }
54 }
55 int main()
56 {
57     cin>>n>>m;
58     ref(i,1,n)
59     {
60         cin>>s;
61         insert();
62     }
63     getfail();
64     work();
65     ref(i,1,tot)if(!a[i].ok&&dp[m][i])
66         (ans+=dp[m][i])%=mod;
67     ans=(mod+mi(26,m)-ans)%mod;
68     cout<<ans<<endl;
69 }

 

相关文章

No Comments, Be The First!
近期评论
    功能
    网站地图xml地图