在8x8的国际象棋棋盘上给定一只骑士（俗称“马”）棋子的位置(R, C)，小Hi想知道从(R, C)开始移动N步一共有多少种不同的走法。
第一行包含三个整数，N，R和C。
对于40%的数据， 1 <= N <= 1000000
对于100%的数据， 1 <= N <= 1000000000 1 <= R, C <= 8
从(R, C)开始走N步有多少种不同的走法。由于答案可能非常大，你只需要输出答案模1000000007的余数。
暴力一点把8X8的棋盘展开
那么每一个 1X64的矩阵代表的是 这个8X8的棋盘里 哪些点会对当前点有共享
预处理一下关系转移矩阵
初始化一下，然后矩阵快速幂即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int size = 255; int dx[] = { -1, 1, -2, 2, -2, 2, -1, 1 }; int dy[] = { -2, -2, -1, -1, 1, 1, 2, 2 }; const int N = 64+6; const long long mod=1e9+7; struct Matrix { long long mat[N][N]; } ; Matrix unit_matrix ; vector<int> son[64+5]; const int k=64; Matrix mul(Matrix a, Matrix b) //矩阵相乘 { Matrix res; for(int i = 0; i < k; i++) for(int j = 0; j < k; j++) { res.mat[i][j] = 0; for(int t = 0; t < k; t++) { res.mat[i][j] += a.mat[i][t] * b.mat[t][j]; res.mat[i][j] %= mod; } } return res; } Matrix pow_matrix(Matrix a, long long m) //矩阵快速幂 { Matrix res = unit_matrix; while(m != 0) { if(m & 1) res = mul(res, a); a = mul(a, a); m >>= 1; } return res; } Matrix get(long long n,long long r,long long cc) { Matrix ori; memset( ori.mat ,0,sizeof ori.mat); ori.mat[0][r*8+cc]=1; Matrix c; memset( c.mat ,0,sizeof c.mat); for(int j=0; j<64; j++) for(int i=0; i<son[j].size(); i++) c.mat[ son[j][i] ][j]=1; Matrix ans = pow_matrix(c, n); ans= mul(ori,ans); return ans; } void pre() { for(int i=0; i<8; i++) { for(int j=0; j<8; j++) { for(int k=0; k<8; k++) { int xx=i+dx[k]; int yy=j+dy[k]; if (xx>=0&&xx<8&&yy>=0&&yy<8) { son[i*8+j].push_back(xx*8+yy); } } } } } int main() { pre(); //初始化单位矩阵 //类似快速幂的 ans=1； 如今是ans=单位矩阵 memset(unit_matrix.mat,0,sizeof unit_matrix.mat); for(int i = 0; i < k; i++) unit_matrix.mat[i][i] = 1; int n,r,c; scanf("%d%d%d",&n,&r,&c); Matrix ans=get(n,r-1,c-1); ll sum=0; for(int i=0;i<64;i++) sum=(sum+ans.mat[0][i])%mod; printf("%lld\n",sum); return 0; }
