[BZOJ1030] [JSOI2007]文本生成器（AC自动机 + DP）

传送门

dp没怎么理解好。。。QAQ

f[i][j]表示长度为i，当前节点为j的方案数

——代码

#include <queue> #include <cstdio> #include <cstring> #define N 100001 #define p 10007 int n, m, cnt, ans, sum = 1; int next[N][26], fail[N], f[101][N]; bool val[N]; char s[N]; std::queue <int> q; inline void insert() val[now] = 1; } inline void make_fail() fail[next[now][i]] = next[fail[now]][i]; val[next[now][i]] |= val[next[fail[now]][i]]; q.push(next[now][i]); } } } int main() make_fail(); for(i = 1; i <= m; i++) sum = (sum * 26) % p; f[0][0] = 1; for(i = 1; i <= m; i++) for(j = 0; j <= cnt; j++) for(i = 0; i <= cnt; i++) if(!val[i]) ans = (ans + f[m][i]) % p; printf("%d\n", ((sum ans) % p + p) % p); return 0; }

　　

上一篇：[BZOJ1031][JSOI2007]字符加密Cipher（后缀数组）

下一篇：火星探险问题

---

DP AC自动机