题目链接

题目描述：

求一个二维矩阵a[ ][ ] = { {1, 1} {1, 0}} n次幂后的a[1][2]，直接矩阵快速幂即可

矩阵快速幂和普通的快速幂相似，只需要将普通的快速幂中的乘法改成矩阵乘法即可

快速幂模板

矩阵快速幂推荐使用结构体去写，用数组会出现莫名其妙的错误

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
struct p{
	ll arr[3][3];
};
const int mod = 10000;
p qc(p a, p b){
	p res;
	res.arr[1][1] = a.arr[1][1] * b.arr[1][1] + a.arr[1][2] * b.arr[2][1];
	res.arr[1][2] = a.arr[1][1] * b.arr[1][2] + a.arr[1][2] * b.arr[2][2];
	res.arr[2][1] = a.arr[2][1] * b.arr[1][1] + a.arr[2][2] * b.arr[2][1];
	res.arr[2][2] = a.arr[2][1] * b.arr[1][2] + a.arr[2][2] * b.arr[2][2];
	res.arr[1][1] %= mod;
	res.arr[1][2] %= mod;
	res.arr[2][1] %= mod;
	res.arr[2][2] %= mod;
	return res;
}
p qpow(p a, ll b){
	p res;
	res.arr[1][2] = res.arr[2][1] = 0;
	res.arr[1][1] = res.arr[2][2] = 1;
	while (b){
		if(b & 1){
			res = qc(res, a);
		}
		b >>= 1;
		a = qc(a, a);
	}
	return res;
}
int main()
{
	ll n;
	while (~scanf("%lld", &n) && n >= 0){
		p ans;
		ans.arr[1][1] = ans.arr[1][2] = ans.arr[2][1] = 1;
		ans.arr[2][2] = 0;
		ans = qpow(ans, n);
		printf("%lld\n", ans.arr[1][2]);
	}
	return 0;
}