[矩阵快速幂]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}
\]
这样就可以矩乘搞了。

示例程序

本文链接:https://zigzagk.top/2018/05/25/bzoj4417
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 CN 许可协议。转载请注明作者和出处QwQ。