You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
53 lines
1.2 KiB
53 lines
1.2 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
typedef long long LL;
|
|
const int N = 10;
|
|
const int MOD = 10000;
|
|
|
|
LL base[N][N], res[N][N];
|
|
|
|
inline void mul(LL C[][N], LL A[][N], LL B[][N]) {
|
|
static LL tmp[N][N];
|
|
memset(tmp, 0, sizeof(tmp));
|
|
for (int i = 1; i <= 2; i++)
|
|
for (int j = 1; j <= 2; j++)
|
|
for (int k = 1; k <= 2; k++)
|
|
tmp[i][j] = (tmp[i][j] + (A[i][k] * B[k][j]) % MOD) % MOD;
|
|
memcpy(C, tmp, sizeof tmp);
|
|
}
|
|
|
|
//快速幂
|
|
inline void qmi(LL k) {
|
|
//初始化结果数组的(i,i)=1
|
|
memset(res, 0, sizeof res);
|
|
res[1][1] = res[1][2] = 1;
|
|
while (k) {
|
|
if (k & 1) mul(res, res, base);
|
|
mul(base, base, base);
|
|
k >>= 1;
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
LL n;
|
|
while (cin >> n) {
|
|
if (n == -1) break;
|
|
if (n == 0) {
|
|
puts("0");
|
|
continue;
|
|
}
|
|
if (n <= 2) {
|
|
puts("1");
|
|
continue;
|
|
}
|
|
//结果矩阵初始化
|
|
memset(base, 0, sizeof base);
|
|
base[1][1] = base[1][2] = base[2][1] = 1;
|
|
//快速幂
|
|
qmi(n - 2);
|
|
//结果
|
|
cout << (res[1][1]) % MOD << endl;
|
|
}
|
|
return 0;
|
|
}
|