现有一个n行m列的棋盘,一只马欲从棋盘的左上角跳到右下角.每一步它向右跳奇数列,且跳到本行或相邻行.跳越期间,马不能离开棋盘.仅有一行,包含两个正整数n m,表示棋盘的规模.
仅有一行,包含一个整数,即跳法种数mod 30011.
题解:一开始搞了个200*200的矩阵,后来又搞了一个150*150的矩阵,最后发现100*100好像也行.不过不管了.
用f[i][j]表示走到第i列,第j行的方案数,那么我们对于所有i为奇数的f维护前缀和s1,再对所有i为偶数的f维护前缀和s0,就可以转移了.
不过.如果用分块矩阵乘法的话,我们要将fs0s1三个矩阵拼起来,一会从s0转移到f,一会从s1转移到f,怎么办呢?维护两个转移矩阵就好了嘛!我们设x表示从s0或s1到i的转移矩阵,具体地转移是这样的:
for(i=1;i<=n;i++)
if(i原文链接<