[POJ2778]DNA Sequence（AC自动机 + DP + 矩阵优化）

传送门

AC自动机加DP就不说了

注意到 m <= 10，所以模式串很少。

而 n 很大就需要 log 的算法，很容易想到矩阵。

但是该怎么构建？

还是矩阵 A(i,j) = ∑A(i,k) * A(k,j)，那么i到j的方案数就是j到k的方案数称k到j的方案数，那么直接矩阵快速幂即可

#include <queue> #include <cstdio> #include <cstring> #define N 100001 #define p 100000 #define LL long long int n, m, cnt, ans; int next[N][4], fail[N], f[101][N]; bool val[N]; char s[N]; std::queue <int> q; struct Matrix }res; inline int idx(char x) 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]); } } } inline Matrix operator * (Matrix x, Matrix y) inline Matrix operator ^ (Matrix x, int y) return ret; } int main() make_fail(); res.n = res.m = cnt; for(i = 0; i <= cnt; i++) res = res ^ m; for(i = 0; i <= cnt; i++) ans = (ans + res.a[0][i]) % p; printf("%d\n", ans); return 0; }

　　

上一篇：[BZOJ1583] [Usaco2009 Mar]Moon Mooing 哞哞叫（队列）

下一篇：[BZOJ4779] [Usaco2017 Open]Bovine Genomics（hash + 二分）

---

DP 矩阵 AC自动机