大炮打蚊子,用了个矩阵快速幂 WA 了。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using vi = vector <i64>;
using M = vector <vi>;
const int MOD = 1e4;
M multi(M a, M b) {
int n = a.size(), t = a[0].size(), m = b[0].size();
M ret(n, vi(m, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (int k = 0; k < t; k++)
ret[i][j] = (ret[i][j] % MOD + ((a[i][k] + MOD) % MOD * (b[k][j] + MOD) % MOD + MOD)) % MOD;
return ret;
}
M fpow(M a, long long k) {
int n = a.size();
M ret(n, vi(n, 0));
for (int i = 0; i < n; i++)
ret[i][i] = 1;
for (; k; a = multi(a, a), k >>= 1)
if (k & 1)
ret = multi(ret, a);
return ret;
}
int main() {
long long n = 2, k;
M A(n, vi(n, 0));
A[0][0] = A[0][1] = A[1][0] = 1;
int T;
cin >> T;
while (T--) {
cin >> k;
if (k <= 2) {
cout << 1 << '\n';
continue;
}
M ret = fpow(A, k);
cout << ret[0][1] << '\n';
}
return 0;
}