题目描述
现有一个n 行m 列的棋盘，一只马欲从棋盘的左上角跳到右下角。每一步它向右跳奇数列，且跳到本行或相邻行。跳越期间，马不能离开棋盘。试求跳法种数mod 30011。
输入输出格式
输入格式：
仅有一行，包含两个正整数n, m，表示棋盘的规模。
输出格式：
仅有一行，包含一个整数，即跳法种数mod 30011。
输入输出样例
输入样例#1：
3 5
输出样例#1：
10
说明
对于10%的数据，1 ≤ n ≤ 10，2 ≤ m ≤ 10；
对于50%的数据，1 ≤ n ≤ 10，2 ≤ m ≤ 10^5；
对于80%的数据，1 ≤ n ≤ 10，2 ≤ m ≤ 10^9；
对于100%的数据，1 ≤ n ≤ 50，2 ≤ m ≤ 10^9。
题解
好久没写矩乘有点忘了
但是这种不难的题还是可以写出来的==
DP式子显然(f[i][j] = (Sum[i-1][j]+Sum[i-1][j-1]+Sum[i-1][j+1]))
那个(Sum[i][j])表示的是第j行前i列的前缀和
然后这样不好做矩乘
可以用(f[i][j])表示第j行前i列的前缀和
然后就是(f[i][j] = f[i-2][j] + f[i-1][j] + f[i-1][j-1] + f[i-1][j+1])
但是这是个前缀和
所以(Ans=f[m-1][n]+f[m-1][n-1])
这样就可以矩乘了
构造一个((1 , n*2))的初始矩阵
前n个表示的是当前列的每一行的(f[][])
后n个表示的是当前列的上一列的每一行的(f[][])
然后转移矩阵就肥肠简单了
只需要把要转移的位置补上1就可以了
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int N = 105 ;
const int mod = 30011 ;
using namespace std ;
int n , m , E ;
int t[N][N] , Ans ;
struct Matrix {
int f[N][N] ;
inline Matrix () { memset(f , 0 , sizeof(f)) ; }
inline void Start() { for(int i = 1 ; i <= E ; i ++) f[i][i] = 1 ; }
inline friend Matrix operator * (Matrix a , Matrix b) {
Matrix temp ;
for(int i = 1 ; i <= E ; i ++)
for(int j = 1 ; j <= E ; j ++)
for(int k = 1 ; k <= E ; k ++)
temp.f[i][j] = (temp.f[i][j] + a.f[i][k] * b.f[k][j]) % mod ;
return temp ;
}
} st , b , Now ;
inline Matrix Fpw(Matrix Base , int k) {
Matrix temp ; temp.Start() ;
while(k) {
if(k & 1) temp = temp * Base ;
Base = Base * Base ; k >>= 1 ;
}
return temp ;
}
int main() {
cin >> n >> m ; t[1][1] = 1 ; E = (n << 1) ;
for(int i = 1 ; i <= n ; i ++) t[2][i] = (t[1][i] + t[1][i - 1] + t[1][i + 1]) % mod ;
if(m <= 3) { Ans = (t[m - 1][n] + t[m - 1][n - 1]) % mod ; printf("%d
",Ans) ; return 0 ; }
for(int i = 1 ; i <= n ; i ++) st.f[1][i] = t[2][i] ;
for(int i = n + 1 ; i <= E ; i ++) st.f[1][i] = t[1][i - n] ;
for(int i = 1 ; i <= n ; i ++) {
b.f[i][i] = 1 ;
if(i != 1) b.f[i - 1][i] = 1 ;
if(i != n) b.f[i + 1][i] = 1 ;
b.f[i + n][i] = 1 ;
}
for(int i = n + 1 ; i <= E ; i ++) b.f[i - n][i] = 1 ;
Now = Fpw(b , m - 3) ; st = st * Now ;
Ans = (st.f[1][n] + st.f[1][n - 1]) % mod ;
cout << Ans << endl ;
return 0 ;
}