【BZOJ1009】【HNOI2008】GT考试

这是一个值得庆祝的时刻!

BZOJ rank终于进2000辣!

另外这道题的题号还是我的生日!

这道题还是挺难的

首先我们可以想出一种dp的思路

用f[i][j]表示到前i位匹配到不jiry串第j位的方案数

那么转移就是枚举下一位c,假设加上了这个c之后匹配到第k位,那么f[i+1][k]+=f[i][j]。

f[0][0]=1,f[0][j]=0(j≠0)

特判i为m时强制只能转移到m。

判断加上c后到匹配第几位可以用KMP预处理。

考虑优化,可以发现转移和i无关,那么用a[j][k]表示匹配到第j位能够转移到匹配到第k位的数字c的取值数

那么用单位矩阵*a矩阵的n次方,也就是a矩阵自乘n次,答案即为

$$\sum_{i=0}^{m-1}a[0][i]$$

矩阵快速幂套一下即可。

总而言之,这道题还是很综合的。

说点什么

您将是第一位评论人!

提醒
wpDiscuz