首页 > 代码库 > [BZOJ1030][JSOI2007]文本生成器
[BZOJ1030][JSOI2007]文本生成器
[BZOJ1030][JSOI2007]文本生成器
试题描述
JSOI交给队员ZYX一个任务,编制一个称之为“文本生成器”的电脑软件:该软件的使用者是一些低幼人群,他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章—— 也就是说,生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词,那么我们说这篇文章是可读的(我们称文章a包含单词b,当且仅当单词b是文章a的子串)。但是,即使按照这样的标准,使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。ZYX需要指出GW文本生成器 v6生成的所有文本中可读文本的数量,以便能够成功获得v7更新版。你能帮助他吗?
输入
输入文件的第一行包含两个正整数,分别是使用者了解的单词总数N (<= 60),GW文本生成器 v6生成的文本固定长度M;以下N行,每一行包含一个使用者了解的单词。这里所有单词及文本的长度不会超过100,并且只可能包含英文大写字母A..Z
输出
一个整数,表示可能的文章总数。只需要知道结果模10007的值。
输入示例
2 2 A B
输出示例
100
数据规模及约定
见“输入”
题解
先构造出 AC 自动机,令 f(i, j) 表示填写了 i 个字母,现在匹配到了 AC 自动机的节点 j,并且从来没有出现过完整单词的方案数,每一位枚举 26 种情况转移即可。
最后用 26m - ∑f(m, j) 就是答案了。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <algorithm> using namespace std; int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); } return x * f; } #define maxnode 6010 #define maxn 110 #define maxa 26 #define MOD 10007 char S[maxn]; int f[maxn][maxnode]; struct AC { int ToT, rt, ch[maxnode][maxa], Fail[maxnode], Q[maxnode], hd, tl; bool val[maxnode]; void init() { ToT = rt = 1; return ; } void Insert(const char* S) { int n = strlen(S), u = rt; for(int i = 0; i < n; i++) { int x = S[i] - ‘A‘; if(!ch[u][x]) ch[u][x] = ++ToT; u = ch[u][x]; } val[u] = 1; return ; } void bfs() { hd = tl = 0; Q[++tl] = rt; while(hd < tl) { int u = Q[++hd]; for(int c = 0; c < maxa; c++) if(ch[u][c]) { int v = ch[u][c], j = Fail[u]; while(j && !ch[j][c]) j = Fail[j]; Fail[v] = ch[j][c] ? ch[j][c] : rt; val[v] |= val[Fail[v]]; Q[++tl] = v; } else ch[u][c] = ch[Fail[u]][c]; } return ; } } sol; int main() { int n = read(), len = read(); sol.init(); for(int i = 1; i <= n; i++) { scanf("%s", S); sol.Insert(S); } sol.bfs(); f[0][1] = 1; int ans = 1; for(int i = 0; i < len; i++) { (ans *= 26) %= MOD; for(int u = 1; u <= sol.ToT; u++) if(f[i][u] && !sol.val[u]) for(int c = 0; c < maxa; c++) { int v = sol.ch[u][c] ? sol.ch[u][c] : 1; f[i+1][v] += f[i][u]; if(f[i+1][v] >= MOD) f[i+1][v] -= MOD; } } for(int u = 1; u <= sol.ToT; u++) if(!sol.val[u]) { ans -= f[len][u]; if(ans < 0) ans += MOD; } printf("%d\n", ans); return 0; }
[BZOJ1030][JSOI2007]文本生成器
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。