必赢亚洲手机app下载


系统怎么着必赢亚洲手机app

慢功出细活

文本生成器

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$。

首先我们协会好$AC$自动机,并且记录一下每一位是或不是可能形成匹配,就是记录每一位的$val$和$last$就行了。

设$f[i][j]$表示统计到文本前$i$位,自动机上第$j$位,没有匹配的方案数,去掉能合作的气象,直接大力转移就行了。

最终大家再用总方案数减去不般配的方案数,就是起码有一个同盟的方案数。

 

  1 //It is made by wfj_2048~
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <complex>
  5 #include <cstring>
  6 #include <cstdlib>
  7 #include <cstdio>
  8 #include <vector>
  9 #include <cmath>
 10 #include <queue>
 11 #include <stack>
 12 #include <map>
 13 #include <set>
 14 #define rhl (10007)
 15 #define inf (1<<30)
 16 #define N (10010)
 17 #define il inline
 18 #define RG register
 19 #define ll long long
 20 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
 21 
 22 using namespace std;
 23 
 24 int f[110][N],q[N],n,m,len,ans;
 25 char s[N];
 26 
 27 struct AC_auto{
 28 
 29     int ch[N][26],val[N],nxt[N],last[N],sz;
 30 
 31     il void insert(char *s,RG int len){
 32     RG int x=0,c;
 33     for (RG int i=1;i<=len;++i){
 34         c=s[i]-65;
 35         if (!ch[x][c]) ch[x][c]=++sz;
 36         x=ch[x][c];
 37     }
 38     val[x]++; return;
 39     }
 40     
 41     il void build(){
 42     RG int h=0,t=0;
 43     for (RG int c=0;c<26;++c)
 44         if (ch[0][c]) nxt[ch[0][c]]=last[ch[0][c]]=0,q[++t]=ch[0][c];
 45     while (h<t){
 46         RG int x=q[++h],v,j;
 47         for (RG int c=0;c<26;++c){
 48         v=ch[x][c]; if (!v){ ch[x][c]=ch[nxt[x]][c]; continue; }
 49         q[++t]=v,nxt[v]=last[v]=0,j=nxt[x]; while (j && !ch[j][c]) j=nxt[j];
 50         nxt[v]=ch[j][c],last[v]=val[nxt[v]] ? nxt[v] : last[nxt[v]];
 51         }
 52     }
 53     return;
 54     }
 55     
 56 }AC;
 57 
 58 il int gi(){
 59     RG int x=0,q=1; RG char ch=getchar();
 60     while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
 61     if (ch=='-') q=-1,ch=getchar();
 62     while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
 63     return q*x;
 64 }
 65 
 66 il int qpow(RG int a,RG int b){
 67     RG int ans=1;
 68     while (b){
 69     if (b&1) ans=ans*a%rhl;
 70     a=a*a%rhl,b>>=1;
 71     }
 72     return ans;
 73 }
 74 
 75 il void work(){
 76     n=gi(),m=gi();
 77     for (RG int i=1;i<=n;++i){
 78     scanf("%s",s+1);
 79     len=strlen(s+1);
 80     AC.insert(s,len);
 81     }
 82     AC.build(); f[0][0]=1;
 83     for (RG int i=0;i<m;++i)
 84     for (RG int j=0;j<=AC.sz;++j){
 85         if (!f[i][j]) continue;
 86         for (RG int k=0;k<26;++k){
 87         if (AC.val[AC.ch[j][k]] || AC.last[AC.ch[j][k]]) continue;
 88         f[i+1][AC.ch[j][k]]+=f[i][j];
 89         if (f[i+1][AC.ch[j][k]]>=rhl) f[i+1][AC.ch[j][k]]-=rhl;
 90         }
 91     }
 92     for (RG int i=0;i<=AC.sz;++i){ ans+=f[m][i]; if (ans>=rhl) ans-=rhl; }
 93     printf("%d\n",(qpow(26,m)-ans+rhl)%rhl); return;
 94 }
 95 
 96 int main(){
 97     File("txt");
 98     work();
 99     return 0;
100 }

 

相关文章

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