rt, WA20

真就除了特判一个没过（

疑似未初始化，输入同样的数据结果不同，出现负数（大雾

代码如下 （马蜂略丑，凑合看吧）

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxSize = 5, mod = 1e4;
struct arr {
	int c[maxSize + 5][maxSize + 5];
	void init() {
		memset(c, 0, sizeof c);
	}
	arr operator * (const arr& b) const {
		arr res;
		int r;
		for(int i = 1; i <= maxSize; i++) {
			for(int k = 1; k <= maxSize; k++) {
				r = c[i][k];
				for(int j = 1; j <= maxSize; j++) {
					res.c[i][j] += b.c[k][j] * r % mod, res.c[i][j] %= mod;
				}
			}
		}
		return res;
	}
	arr operator % (int b) const {
		arr res;
		if(b == 0)return res;
		for(int i = 1; i <= maxSize; i++)
			for(int j = 1; j <= maxSize; j++)
				res.c[i][j] = c[i][j] % b;
		return res;
	}
	arr operator + (const arr& b) const {
		arr res;
		for(int i = 1; i <= maxSize; i++)
			for(int j = 1; j <= maxSize; j++)
				res.c[i][j] = c[i][j] + b.c[i][j], res.c[i][j] %= mod;
		return res;
	}
	arr operator ^ (int b) const {
		arr res, bas;
		for(int i = 1; i <= maxSize; i++)res.c[i][i] = 1;
		for(int i = 1; i <= maxSize; i++)
			for(int j = 1; j <= maxSize; j++)
				bas.c[i][j] = c[i][j] % mod;
		while(b > 0) {
			if(b & 1)res = res * bas % mod;
			bas = bas * bas % mod;
			b >>= 1;
		}
		return res;
	}
};
signed main() {
	int n;
	arr x, y, z;
	x.init(), y.init(), z.init();
	x.c[1][1] = x.c[2][2] = 1;
	y.c[1][2] = y.c[2][1] = y.c[2][2] = 1;
	cin >> n;
	if(n == 0) {
		cout << "0\n";
		return 0;
	}
	if(n == 1 || n == 2) {
		cout << "1\n";
		return 0;
	}
	y = y ^ (n - 1);
	z = x * y;
	cout << z.c[1][1] % 10000 << "\n";
	return 0;
}