首页 > 代码库 > 【BZOJ1030】[JSOI2007]文本生成器 AC自动机+动态规划
【BZOJ1030】[JSOI2007]文本生成器 AC自动机+动态规划
【BZOJ1030】[JSOI2007]文本生成器
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
题解:由于直接求可读文本的数量比较困难,那我们不妨求出所有不可读的文本的数量,再用总数减去不可读的文本数量就行了。
用f[i][j]表示文本的第i位匹配AC自动机中的第j个元素的方案数,我们还是用fail直接修改节点的儿子,然后就可以直接进行转移了。
还是要注意用fail修改儿子时,也要同时传递cnt(是否有单词在该点结束)
#include <cstdio> #include <cstring> #include <iostream> #include <queue> using namespace std; const int mod=10007; struct node { int ch[26],fail,cnt; }p[6010]; int n,m,tot,sum,ans; int f[110][6010]; char w[110]; queue<int> q; int main() { scanf("%d%d",&n,&m); int i,j,k,u,t; tot=1; for(i=1;i<=n;i++) { scanf("%s",w); k=strlen(w); for(j=0,u=1;j<k;j++) { if(!p[u].ch[w[j]-‘A‘]) p[u].ch[w[j]-‘A‘]=++tot; u=p[u].ch[w[j]-‘A‘]; } p[u].cnt=1; } q.push(1); while(!q.empty()) { u=q.front(),q.pop(); for(i=0;i<26;i++) { if(!p[u].ch[i]) { if(u==1) p[u].ch[i]=1; else p[u].ch[i]=p[p[u].fail].ch[i]; continue; } q.push(p[u].ch[i]); if(u==1) { p[p[u].ch[i]].fail=1; continue; } p[p[u].ch[i]].fail=p[p[u].fail].ch[i]; p[p[u].ch[i]].cnt|=p[p[p[u].fail].ch[i]].cnt; } } f[0][1]=1; for(i=1;i<=m;i++) for(j=1;j<=tot;j++) if(!p[j].cnt) for(k=0;k<26;k++) f[i][p[j].ch[k]]=(f[i][p[j].ch[k]]+f[i-1][j])%mod; for(i=1;i<=tot;i++) if(!p[i].cnt) ans=(f[m][i]+ans)%mod; for(i=1,sum=1;i<=m;i++) sum=(sum*26)%mod; printf("%d",(sum-ans+mod)%mod); return 0; }
【BZOJ1030】[JSOI2007]文本生成器 AC自动机+动态规划
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。