情之所至,甘之如饴

题意

现有一个$n$行$m$ 列的棋盘,一只马欲从棋盘的左上角跳到右下角。每一步它向右跳奇数列,且跳到本行或相邻行。跳越期间,马不能离开棋盘。例如,当$n = 3, m = 10$ 时,下图是一种可行的跳法。

img

试求跳法种数$mod\ 30011$。

解法

本题为采用矩阵速幂优化的动态规划,首先需要想出朴素的转移方程。

10pts: 朴素做法

我们用$dp[i][j]$表示超级跳马跳到$(i,j)$的总方案数,这样最终只需求出$dp[n][m]$即可。

考虑马能从什么地方跳到$(i,j)$。根据题目条件,从行和列的角度分别考虑。

首先考虑行。第$i$行,第$i+1$行和第$i-1$行都可以跳到第$i$行。

接着考虑列,只要是和第$j$列相差奇数列的列都可以跳到第$j​$列。因此

如果我们直接用朴素的循环计算,复杂度为$O(nm^2)$,只能得到10分,因此考虑在计算过程中优化。

50pts:前缀和优化

100pts:矩阵快速幂



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:726.4k