hihoCoder 1504-骑士游历

hihoCoder 1504-骑士游历

#1504 : 骑士游历

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

描述

在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),问走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行即可,没必要再构造一个只含一个元素的矩阵,再左乘了。

#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;
}

本代码提交AC,用时412MS。

One thought on “hihoCoder 1504-骑士游历

  1. Pingback: POJ 3070-Fibonacci | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *