首页 > 代码库 > BZOJ1030: [JSOI2007]文本生成器
BZOJ1030: [JSOI2007]文本生成器
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1030
1030: [JSOI2007]文本生成器
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 3831 Solved: 1565
[Submit][Status][Discuss]
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
A
B
Sample Output
100
HINT
Source
将单词建出AC自动机,设f[i][j]代表生成到第i位,生成的文章没有出现单词,文章匹配到AC自动机上编号为j的节点的方案数。
WA了无数次。。。话说难道我以前写AC自动机都写错了???
#include<cstdio> #include<cstring> #define maxn 65 #define maxm 105 #define p 10007 using namespace std; int n,m,ans,tot,ch[maxn*maxm][30],fail[maxn*maxm],f[maxm][maxn*maxm]; bool end[maxn*maxm]; char s[maxm]; int read(){ int x=0,f=1;char ch; for(ch=getchar();ch<‘0‘||ch>‘9‘;ch=getchar())if(ch==‘-‘)f=-1; for(;ch>=‘0‘&&ch<=‘9‘;ch=getchar())x=x*10+ch-‘0‘; return x*f; } int power(int x,int y){ int z=1; for(;y;x=x*x%p,y>>=1)if(y&1)z=z*x%p; return z; } int head,tail,d[maxn*maxm]; int main(){ m=read();n=read();tot=1; for(int i=0;i<26;i++)ch[0][i]=1; for(int i=1;i<=m;i++){ scanf("%s",s+1); for(int j=1,k=1;j<=strlen(s+1);j++){ if(!ch[k][s[j]-‘A‘])ch[k][s[j]-‘A‘]=++tot;k=ch[k][s[j]-‘A‘]; if(j==strlen(s+1))end[k]=1; } } head=tail=1;d[1]=1; while(head<=tail){ for(int i=0;i<26;i++)if(ch[d[head]][i]){ int j=fail[d[head]];while(!ch[j][i])j=fail[j];j=ch[j][i]; fail[ch[d[head]][i]]=j;if(end[j])end[ch[d[head]][i]]=1;d[++tail]=ch[d[head]][i]; } head++; } f[0][1]=1; for(int i=0;i<n;i++){ for(int j=1;j<=tot;j++){ if(f[i][j]==0||end[j])continue; for(int l=0;l<26;l++){ int k=j;while(k&&!ch[k][l])k=fail[k];k=ch[k][l]; f[i+1][k]=(f[i+1][k]+f[i][j])%p; } } } for(int i=1;i<=tot;i++)if(!end[i])ans=(ans+f[n][i])%p; printf("%d\n",(power(26,n)-ans+p)%p); return 0; }
BZOJ1030: [JSOI2007]文本生成器
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。