Tag Archives: 矩阵

hihoCoder 1504-骑士游历

hihoCoder 1504-骑士游历

#1504 : 骑士游历

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

在8×8的国际象棋棋盘上给定一只骑士(俗称“马”)棋子的位置(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),问走N步共有多少种走法。 这题我最开始是用DFS做的,但是只能过一部分数据,对于100%的数据,N最大居然可以达到1000000000,太恐怖了。 后来问了大神,说是用矩阵快速幂来做,恍然大悟。 在我介绍的马尔可夫聚类算法博客中,初始时给定一个图的邻接矩阵A,则$$B=A^n$$中B[i][j]表示从i点到j点走n步的方案数。MCL算法为了满足随机游走,还加上了单位矩阵,具体的例子可以看我那篇博客的图。 这个题就是用MCL的方法来做的。国际象棋的棋盘是8*8的,也就是有64个位置,初始时我们可以算到每个点走一步能走到的位置,这样就能得到一个64*64的邻接矩阵A。然后使用快速幂计算$$B=A^n$$。最后把起始点(R,C)转换为一个1*64的行向量,左乘B矩阵,得到一个1*64的行向量。这样做的含义就是从(R,C)出发,走n步到达每个点的方案数。把结果行向量的元素累加起来就是总的方案数。 完整代码如下,最后一步时,直接取出幂矩阵的第idx行即可,没必要再构造一个只含一个元素的矩阵,再左乘了。 [cpp] #include<iostream> #include<vector> using namespace std; typedef long long LL; vector<vector<int>> dirs = { { 1,2 },{ 1,-2 },{ 2,1 },{ 2,-1 },{ -2,1 },{ -2,-1 },{ -1,2 },{ -1,-2 } }; const int MAXN = 8; const LL MOD = 1000000007; vector<vector<LL>> matrix(MAXN*MAXN, vector<LL>(MAXN*MAXN, 0)); inline bool ok(const int &x, const int &y) { return x >= 0 && x < MAXN && y >= 0 && y < MAXN; } inline int id(const int &x, const int &y) { return x*MAXN + y; } void init() { for (int i = 0; i < MAXN; ++i) { for (int j = 0; j < MAXN; ++j) { for (int k = 0; k < dirs.size(); ++k) { int x = i + dirs[k][0], y = j + dirs[k][1]; if (ok(x, y))matrix[id(i, j)][id(x, y)] = 1; } } } } vector<vector<LL>> multi(const vector<vector<LL>>& mat1, const vector<vector<LL>>& mat2) { vector<vector<LL>> ans(MAXN*MAXN, vector<LL>(MAXN*MAXN, 0)); for (int i = 0; i < MAXN*MAXN; ++i) { for (int j = 0; j < MAXN*MAXN; ++j) { for (int k = 0; k < MAXN*MAXN; ++k) { ans[i][j] = (ans[i][j] + mat1[i][k] * mat2[k][j]) % MOD; } } } return ans; } vector<vector<LL>> pow(vector<vector<LL>>& mat, int n) { vector<vector<LL>> ans(MAXN*MAXN, vector<LL>(MAXN*MAXN, 0)); for (int i = 0; i < MAXN*MAXN; ++i)ans[i][i] = 1; // 单位阵 while (n != 0) { if (n & 1)ans = multi(ans, mat); mat = multi(mat, mat); n >>= 1; } return ans; } int main() { int n, r, c; scanf("%d %d %d", &n, &r, &c); –r; –c; init(); vector<vector<LL>> finalMat = pow(matrix, n); int idx = id(r, c); // first way: long long ans = 0; for (int i = 0; i < MAXN*MAXN; ++i)ans = (ans + finalMat[idx][i]) % MOD; printf("%lld\n", ans); // second way: //vector<vector<LL>> one(MAXN*MAXN, vector<LL>(MAXN*MAXN, 0)); //one[idx][idx] = 1; //one = multi(one, finalMat); //long long ans = 0; //for (int i = 0; i < MAXN*MAXN; ++i) { // for (int j = 0; j < MAXN*MAXN; ++j) { // ans = (ans + one[i][j]) % MOD; // } //} //printf("%lld\n", ans); return 0; } [/cpp] 本代码提交AC,用时412MS。]]>