夢に僕らで帆を張って
来るべき日のために夜を超え

标签 矩阵乘法 下的文章

October 27, 2019

洛谷P3193/HNOI2008 GT考试

题意求有多少个$n$位的字符串不包含$m$位的字符串数据范围:$n \le 10^9,m \le 20,k \le 1000$题解用$f[i][j]$表示长串考虑到第$i$个字符,短串中最多能匹配到第$j$个字符的方案数,那么答案就是$$\sum_{i=0}^{m-1} f[n][i]$$考虑如何从$f[i-1][k]$转移到$f[i][j]$:预处理一个数组$g[k][j]$表示短串中前缀...