参考博客:
http://blog.zhengyi.one/fibonacci-in-logn.html
原文是用python实现,这里改写成C++
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 1000000007;
typedef long long LL;
struct matrix{
LL m[2][2];
};
const matrix E = {
1, 1,
1, 0,
};
matrix multi(const matrix &a, const matrix &b) // 矩阵乘法
{
matrix c;
for(int i=0; i<2; i++)
{
for(int j=0; j<2; j++)
{
c.m[i][j] = 0;
for(int k=0; k<2; k++)
c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
}
}
return c;
}
matrix pow_mod(LL n) // 快速幂运算
{
matrix res = E, a = E;
while(n)
{
if(n&1)
res = multi(res, a);
a = multi(a, a);
n = n/2;
}
return res;
}
int main()
{
LL n;
scanf("%lld", &n);
printf("%lld\n", pow_mod(n).m[0][1]);
return 0;
}