hihoCoder 1504-骑士游历

hihoCoder 1504-骑士游历

输出

2 1 1

12

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


One thought on “hihoCoder 1504-骑士游历”

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