BZOJ1009求解

表示BZOJ1009卡了我一天了。。。
没思路。。于是去搜题解。。
结果果然又是新技能

话说我为什么天天都会遇到新技能（显然我太弱了）
甚至题解也看不懂。。。
因为我对字符串处理和矩阵这俩玩意一无所知= =
果然还是太弱了。。然而并不想弃疗。。
DP已经懂了，然而。。然而。。。
然而我现在还是没搞懂是怎么把DP压缩成矩阵加速的（原谅我没写过矩乘(捂脸)）
如果是我根本没实力刷掉这题，那我该找什么知识点

。。。求指教

自顶

求好心的学长讲解下

然而是什么题啊

这个题，先kmp求出nxt数组后，设f[i][j]表示长度为i的串，匹配到了位置j的方案数。
那么对于f[i][j]，枚举下一个数字，根据nxt数组可以转移到f[i+1][k]，然后构造转移矩阵A和列向量B，B=(f[0][0],f[0][1],...,f[0][m])，A可以由DP得到，那么A*B的结果就是(f[1][0],f[1][1],...,f[1][m])，所以A^n*B的结果就是(f[n][0],f[n][1],...,f[n][m])。然后用快速幂算出A^n之后，再乘以B即可得到答案。时间复杂度为O(m^3logn)。

我猜楼主在版刷bzoj

http://www.cnblogs.com/

JSZX11556

/p/4770610.html

其实可以不要按照顺序

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

8回复贴，共1页

<<返回noip吧

分享到:

日	一	二	三	四	五	六