hihoCoder 1504-骑士游历

---

在国际象棋上，给定马的起点(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。]]>