Description
In the Fibonacci integer sequence,
F
0 = 0,
F
1 = 1, and
F
n =
F
n
− 1 +
F
n
− 2 for
n ≥ 2.
Input
a single line containing n (where 0 ≤
n ≤ 100,000,000,000)
Output
print
F
n mod 1000000007 in a single line.
Sample Input
99999999999
Sample Output
669753982
Hint
An alternative formula for the Fibonacci sequence is
As a reminder, matrix multiplication is associative, and the product of two 2 × 2 matrices is given by
Also, note that raising any 2 × 2 matrix to the 0th power gives the identity matrix:
Source
Unknown
思路：一开始想着要暴力的办法，或者用python，但还是tle了，然后发现这玩意儿可以用矩阵快速幂，就来一波骚操作了。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eps 1e-9
#define pi acos(-1)
const int inf =
0x3f3f3f3f;
const int mod =
1000000007;
const int maxn =
1000 +
8;
ll n;
struct matrix
{
ll m[2][
2];
}b, tp, res, init;
matrix mul(matrix a, 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] += (a.m[i][k] * b.m[k][j]) %
mod;
c.m[i][j] %=
mod;
}
}
}
return c;
}
matrix matrix_mi(matrix p, ll k)
{
matrix t =
res;
while(k)
{
if(k &
1)
t =
mul(t, p);
k >>=
1;
p =
mul(p, p);
}
return t;
}
int main()
{
std::ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for(
int i =
0; i <
2; i++
)
for(
int j =
0; j <
2; j++
)
{
if(i ==
1 && j ==
1)
init.m[i][j] =
0;
else
init.m[i][j] =
1;
}
cin >>
n;
b =
init;
for(
int i =
0; i <
2; i++
)
for(
int j =
0; j <
2; j++
)
if(i ==
j)
res.m[i][j] =
1;
else
res.m[i][j] =
0;
tp =
matrix_mi(b, n);
cout << tp.m[
0][
1] <<
'\n';
return 0;
}
转载于:https://www.cnblogs.com/RootVount/p/11469372.html
相关资源：JAVA上百实例源码以及开源项目
