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.
54 lines
1.1 KiB
54 lines
1.1 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
typedef long long LL;
|
|
const int N = 10;
|
|
const int MOD = 1e9 + 7;
|
|
|
|
//矩阵声明
|
|
struct JZ {
|
|
LL m[N][N];
|
|
} res, base;
|
|
|
|
inline JZ mul(JZ A, JZ B) {
|
|
JZ C;
|
|
memset(C.m, 0, sizeof(C.m));
|
|
for (int i = 1; i <= 2; i++)
|
|
for (int j = 1; j <= 2; j++)
|
|
for (int k = 1; k <= 2; k++) {
|
|
C.m[i][j] = (C.m[i][j] + (A.m[i][k] * B.m[k][j]) % MOD) % MOD;
|
|
}
|
|
return C;
|
|
}
|
|
|
|
//快速幂
|
|
inline void qmi(LL k) {
|
|
memset(res.m, 0, sizeof res.m);
|
|
res.m[1][1] = res.m[1][2] = 1; // f(1)=1,f(2)=1 乘一次矩阵就是f(3),所以f(n)就是n-2次方
|
|
while (k) {
|
|
if (k & 1) res = mul(res, base);
|
|
base = mul(base, base);
|
|
k >>= 1;
|
|
}
|
|
}
|
|
int main() {
|
|
LL n;
|
|
cin >> n;
|
|
if (n <= 2) {
|
|
puts("1");
|
|
return 0;
|
|
}
|
|
//结果矩阵初始化
|
|
memset(base.m, 0, sizeof base.m);
|
|
base.m[1][1] = base.m[1][2] = base.m[2][1] = 1;
|
|
/*
|
|
1 1
|
|
1 0
|
|
base 矩阵
|
|
*/
|
|
//快速幂
|
|
qmi(n - 2);
|
|
//结果
|
|
cout << (res.m[1][1]) % MOD << endl;
|
|
return 0;
|
|
}
|