BZOJ1030: [JSOI2007]文本生成器(AC自动机)
2018-07-03 01:00:54来源:博客园 阅读 ()
Submit: 5984 Solved: 2523
[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
A
B
Sample Output
HINT
Source
感觉自己好菜啊这种题都想不出来qwq。。
刚开始想的是容斥—>把所有合法的统计出来再减去重复的!!没错我就这么xjb容斥了半个小时qwq。。
看了一下大佬的题解瞬间思路明了。。。
考虑经典补集转化思想:这题问的是可读的,我们可以转化为总的-不可读的。
总的就是$26^m$
不可读的考虑DP。设$f[i][j]$表示长度为$i$时,在自动机上第$j$个位置有多少不可读的情况
开始时$f[0][0] = 1$,转移的时候枚举一下出边
注意!!如果一个点的$fail$指针指向的位置不可读,那么该节点也是不可读的!
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<cmath> using namespace std; const int MAXN = 1e5 + 10, B = 26, mod = 10007; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M; int ch[MAXN][26], fail[MAXN], tot = 0, root = 0, val[MAXN]; char s[101]; void insert(char *s) { int N = strlen(s + 1), now = root; for(int i = 1; i <= N; i++) { int x = s[i] - 'A'; if(!ch[now][x]) ch[now][x] = ++tot; now = ch[now][x]; } val[now] = 1;//不能经过 } void GetFail() { queue<int> q; for(int i = 0; i < B; i++) if(ch[root][i]) q.push(ch[root][i]); while(!q.empty()) { int p = q.front(); q.pop(); for(int i = 0; i < B; i++) if(ch[p][i]) fail[ch[p][i]] = ch[fail[p]][i], q.push(ch[p][i]); else ch[p][i] = ch[fail[p]][i]; val[p] |= val[fail[p]]; } } int f[101][MAXN]; // 当前长度为i,在自动机的地j号节点 int solve() { f[0][0] = 1; for(int i = 1; i <= M; i++) { for(int j = 0; j <= tot; j++) { for(int k = 0; k < B; k++) {//枚举出边 int son = ch[j][k]; if(val[son]) continue; f[i][son] = (f[i][son] % mod+ f[i - 1][j] % mod) % mod; } } } int ans = 0; for(int i = 0; i <= tot; i++) ans = (ans + f[M][i] % mod) % mod; int sum = 1; for(int i = 1; i <= M; i++) sum = (26 * sum) % mod; return (sum - ans + mod) % mod; } main() { #ifdef WIN32 freopen("a.in", "r", stdin); #endif scanf("%d %d", &N, &M); for(int i = 1; i <= N; i++) scanf("%s", s + 1), insert(s); GetFail(); printf("%d", solve() % mod); }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 洛谷P4051 [JSOI2007]字符加密 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash