传送门
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; }
上一篇：[BZOJ1589] [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果（tarjan缩点 + 记忆化搜索）
下一篇：[BZOJ4779] [Usaco2017 Open]Bovine Genomics（hash + 二分）
DP AC自动机 矩阵
