ZigZagK

Never give up fighting!

[矩阵快速幂]BZOJ4417(Shoi2013)【超级跳马】题解

题目概述

现有一个 \(n\)\(m\) 列的棋盘,一只马欲从棋盘的左上角跳到右下角。每一步它向右跳奇数列,且跳到本行或相邻行。跳越期间,马不能离开棋盘。试求跳法种数 \(mod\ 30011\)

解题报告

我好菜啊,怎么这都不会啊,Orz ChesterKing。首先先写柿子: \[
f_{i,j}=\sum_{k}f_{i-(2k-1),j-1}+f_{i-(2k-1),j}+f_{i-(2k-1),j+1}
\]
\(m\) 这么大应该是矩乘,但是这样肯定没法做啊QAQ。我们要想办法把这个柿子变成只和相邻几个有关,怎么办呢?想削掉 \(\Sigma\) 当然只能记录前缀和啦XD。

所以记录 \(sum_{0/1,j}\) 表示当前前面和后面的两列前缀和,转移: \[
sum'_{0,i}=sum_{1,i}\\
sum'_{1,i}=sum_{0,i}+sum_{1,i-1}+sum_{1,i}+sum_{1,i+1}
\]
这样就可以矩乘搞了。

示例程序

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

不资瓷Markdown;资瓷LaTeX:行内公式\(...\),行间公式\[...\]