louhc

题解

未归档(78)

/ 注册

全部文章 / 题解（共1篇）

题解 | 信息学奥赛一本通 GT考试

思路先不考虑数据范围,我们设表示当前构造到第位,已经匹配了位的方案数.最终答案即为我们可以写出一个递推式,是我们要求的系数.我们可以使用KMP来求系数.只要求出前位(长度为)与相同,下一位的数字为时,与最大的匹配长度.对于每一个,,很明显不能承受.但是系数每次转移都不会变,因此直接用矩阵快速幂优化...

字符串矩阵乘法快速幂 KMP

2019-08-24

0 552