【luogu P1962 斐波那契数列】题解

题目链接：https://www.luogu.org/problemnew/show/P1962

给你篇dalao的blog自己看吧，把矩阵快速幂的板子一改就OK

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 using namespace std;
 6 struct Matrix{
 7     long long m[3][3];
 8 }A,E,ans;
 9 long long n,k, mod = 1000000007;
10 Matrix mul(Matrix A,Matrix B)
11 {
12     Matrix C;
13     for(int i = 1; i <= 2; i++)
14         for(int j = 1; j <= 2; j++)
15         {
16             C.m[i][j] = 0;
17             for(int k = 1; k <= 2; k++)
18                 C.m[i][j] = (C.m[i][j]+(A.m[i][k]*B.m[k][j]))%mod;    
19         }
20     return C;
21 }
22 Matrix fast(Matrix A, long long k)
23 {
24     Matrix S = E;
25     while(k)
26     {
27         if(k&1) S = mul(S,A);
28         A = mul(A,A);
29         k = k>>1;
30     }
31     return S;
32 }
33 int main(){
34     
35     scanf("%lld",&k);
36     
37     E.m[2][2] = 1;
38     E.m[1][1] = 1;
39     A.m[1][1] = 1;
40     A.m[1][2] = 1;
41     A.m[2][1] = 1;
42     ans = fast(A,k);
43         
44     printf("%lld ",(ans.m[2][1])%mod);
45     return 0;
46 }

隐约雷鸣，阴霾天空，但盼风雨来，能留你在此。

隐约雷鸣，阴霾天空，即使天无雨，我亦留此地。

【luogu P1962 斐波那契数列】 题解

【luogu P1962 斐波那契数列】题解