描述
在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的余数。
样例输入
2 1 1
样例输出
12
对于棋盘中任意一个点(R,C)，都有多个位置可跳。
比如：(R,C)可以跳到(R+1,C+2)的位置。
为了描述这种关系，可以建立一个64x64的邻接矩阵；这个邻接矩阵第一维对应8X8中的每一个点，第二维维护第一维的点可跳的位置。
对于这样的一个矩阵，用起始矩阵1X64乘以邻接矩阵64X64，得到的一个1X64的矩阵，这个矩阵的点上值表示从起始位置走一步，到达该位置有多少中方案。（参考离散数学和线性代数）
因此可以将这个乘以矩阵的过程转化为矩阵快速幂，迅速求得结果。
之前并不了解过这种方法，今天做题遇到的，回去看看线性代数（只怪当初没好好学）。
为了加深这个题，找了与之相似的题目: http://lightoj.com/volume_showproblem.php?problem=1122
此题题解：http://www.cnblogs.com/aiterator/p/6685972.html
#include<bits/stdc++.h>
using namespace std;
typedef vector<unsigned long long> vec;
typedef vector<vec> mat;
const unsigned long long mod = 1000000007;
int dir[8][2] = { {1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1} };
mat mul(mat &a, mat &b)
{
mat c(a.size(), vec(b[0].size(), 0));
for(int i=0; i<a.size(); ++ i)
{
for(int j=0; j<b[0].size(); ++ j)
{
for(int k=0; k<b.size(); ++ k)
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
}
}
return c;
}
mat pow(mat &a, unsigned long long n)
{
mat b(a.size(), vec(a[0].size(), 0));
for(int i=0; i<a.size(); ++ i)
b[i][i] = 1;
while(n > 0)
{
if(n & 1)
b = mul(b, a);
a = mul(a, a);
n >>= 1;
}
return b;
}
int main()
{
int n, r, c;
cin >> n >> r >> c;
mat a(64, vec(64, 0));
for(int i=0; i<8; ++ i)
{
for(int j=0; j<8; ++ j)
{
for(int k=0; k<8; ++ k)
{
int x = i + dir[k][0], y = j + dir[k][1];
if((x >= 0 && x < 8 && y >= 0 && y < 8) == false)
continue;
int u = x * 8 + y, v = i * 8 + j;
a[u][v] = a[v][u] = 1;
}
}
}
mat b(1, vec(64, 0));
b[0][(r-1)*8 + c-1] = 1;
mat s = pow(a, n);
mat d = mul(b, s);
unsigned long long ans = 0;
for(auto &i: d)
{
for(auto &j: i)
ans = (ans + j) % mod;
}
cout << ans << endl;
return 0;
}