xyq0220

分类

未归档(101) 题解(3)

/ 注册

全部文章（共1篇）

HDU-2243 考研路茫茫——单词情结 AC自动机+矩阵快速幂

题意给n个模式串，问有多少个长度不超过L的字符串中至少出现一种模式串。分析有多少个长度为L的字符串中不出现任意一个模式串的题已经做过，构造一个矩阵\(A\)，答案\(s_n\)即为\(s_0*A^n\) 用矩阵快速幂算下就行了，这题的计算方法就显然是\(26^0+26^1+26^2+\...

AC自动机矩阵快速幂

2019-09-26

0 485