#include <iostream>
using namespace std;

const int num = 2;
const int mod = 10000;

struct mat {
	int m[num][num];
};

mat I{
	1,0,
	0,1
};

mat mul(mat a, mat b) {
	mat ans;
	for(int i=0;i<num;i++)
		for (int j = 0; j < num; j++) {
			ans.m[i][j] = 0;
			for (int k = 0; k < num; k++)
				ans.m[i][j] += (a.m[i][k] * b.m[k][j]);
			ans.m[i][j] %= mod;
		}
	return ans;
}

mat quick_pow(mat a, long long b) {
	mat ans = I;
	mat tmp = a;
	while (b > 0) {
		if (b & 1)
			ans = mul(ans, tmp);
		tmp = mul(tmp, tmp);
		b >>= 1;
	}
	return ans;
}

int main() {
	long long n;
	mat a{
		1,1,
		1,0
	};
	while (cin >> n&&n!=-1) {
		mat tmp;
		tmp = quick_pow(a, n);
		cout << tmp.m[0][1] << endl;
	}
	return 0;
}

• Re:矩阵快速幂 (863) 20172203002 2018-02-01 09:33:29