bzoj 1009: [HNOI2008]GT考试 KMP+矩阵乘法+dp

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1009


神仙题!

$f[i][j]$ 表示前 $i$ 位数字,它的最后 $j$ 位与不吉利串匹配的方案数

有一种方案可以 $f[i][j]=f[i-1][j-1]+1$ ,但是其他的方案并不用从 $f[i-1][0]$ 重新开始扫,而是找 $KMP$ 的 $fail$ 就可以了。

随后我们发现是一堆加法,并且所有转移都是一样的,所以就可以用矩阵乘法来优化了。

(我并不太想写题解,我只是想记录一下这个神仙题)

 

发表评论