非常经典的矩阵乘法板子题。
构造这样的一个矩阵乘法公式,然后第几项就是A^(n-1),来个快速幂就行。
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 10000;
typedef pair<int, int> PII;
int n;
const int N = 32;
vector<vector<int>> f = {{0, 1}};
vector<vector<int>> A = {{0, 1}, {1, 1}};
vector<vector<int>> mul(vector<vector<int>> a, vector<vector<int>> b) {
int n = a.size(), m = b[0].size(), p = a[0].size();
vector<vector<int>> c(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < p; k++) {
c[i][j] = (c[i][j] + a[i][k] * b[k][j] % MOD) % MOD;
}
}
}
return c;
}
vector<vector<int>> qmi(vector<vector<int>> & a, int x) {
vector<vector<int>> res = {{0, 1}};
vector<vector<int>> base = a;
for (int i = 0; i < N; i++) {
if (x & (1 << i)) {
res = mul(res, base);
}
base = mul(base, base);
}
return res;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
while (cin >> n && n != -1) {
if (n == 0) {
cout << 0 << endl;
continue;
}
auto res = qmi(A, n);
cout << res[0][0]<< endl;
}
return 0;
}