《骑士游历》题目分析

本题是一道图论+矩阵快速幂的题目。

首先对于一个无向图G，假设A是G的邻接矩阵(如果ij之间右边，Aij=1;否则Aij=0)，An = A^n是邻接矩阵的n次方。

那么An(i, j)实际上就是从点i经过恰好n条边到达点j的路径数。

所以对于本题，我们可以将棋盘上64个格子看成64个点，如果两个格子一步跳马可达，就在相应的点连一条边。这样构造出邻接矩阵A。

然后就是求A^n，注意n非常大，需要用矩阵快速幂。

最后就是求所有方案数。假设(R, C)对应的点是s，那么总方案数就是Sigma A(s, k) | k = 1..64