P3390 【模板】矩阵快速幂

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<math.h>
 4 #include<string.h>
 5 using namespace std;
 6 typedef long long ll;
 7 const ll mod=1e9+7;
 8 struct node
 9 {
10     ll a[10][10];
11 }ans,A,B;
12 node mat(node x,node y)
13 {
14     node c;
15     for(int i=0;i<=1;i++)
16     for(int j=0;j<=1;j++)
17         c.a[i][j]=0;
18     for(int i=0;i<=1;i++)
19         for(int j=0;j<=1;j++)
20         for(int k=0;k<=1;k++)
21             c.a[i][j]=(c.a[i][j]+x.a[i][k]*y.a[k][j]%mod)%mod;
22     return c;
23 }
24 void init()
25 {
26     A.a[0][0]=1;A.a[0][1]=1;
27     A.a[1][0]=1;A.a[1][1]=0;
28 }
29 void quick_mod(ll n)
30 {
31     for(int i=0;i<=1;i++)
32     for(int j=0;j<=1;j++)
33         if(i==j) B.a[i][j]=1;
34         else B.a[i][j]=0;
35     init();
36     while(n){
37         if(n&1) B=mat(B,A);
38         A=mat(A,A);
39         n>>=1;
40     }
41 }
42 int main()
43 {
44     ll n;
45     scanf("%lld",&n);
46     if(n==1||n==2){
47         printf("1\n");
48         return 0;
49     }
50     quick_mod(n-2);
51     ans.a[0][0]=ans.a[0][1]=1;
52     ans=mat(ans,B);
53     printf("%lld\n",ans.a[0][0]);
54     return 0;
55 }