【洛谷P1939】矩阵加速模板

首先看一下斐波那契数列的矩阵快速幂求法：

则该矩阵为

0 1

1 1

第一行第一列：f[n-2]*0+f[n-1]*1=f[n-1]

第一行第二列：f[n-2]*1+f[n-1]*1=f[n]

同理，对于本题：

那么这个矩阵为

0 0 1

1 0 0

0 1 1

代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #define ll long long
 5 using namespace std;
 6 const ll RQY = 1000000007;
 7 ll t,n;
 8 struct Matrix
 9 {
10     ll m[4][4];
11 } A,ANS,One;
12 Matrix times(Matrix X,Matrix Y)
13 {
14     Matrix Ans;
15     for(int i=1;i<=3;i++)
16      for(int j=1;j<=3;j++)
17       Ans.m[i][j]=(X.m[i][1]*Y.m[1][j]%RQY+X.m[i][2]*Y.m[2][j]%RQY+X.m[i][3]*Y.m[3][j]%RQY)%RQY;
18     return Ans;
19 }
20 Matrix qpow(Matrix X,ll k)
21 {
22     Matrix S=One;
23     while(k)
24     {
25         if(k&1) S=times(S,X);
26         k>>=1;
27         X=times(X,X);
28     }
29     return S;
30 }
31 int main()
32 {
33     scanf("%lld",&t);
34     One.m[1][1]=1;
35     One.m[2][2]=1;
36     One.m[3][3]=1;
37     A.m[1][3]=1;
38     A.m[2][1]=1;
39     A.m[3][2]=1;
40     A.m[3][3]=1;
41     while(t--)
42     {
43         scanf("%lld",&n);
44         n-=1;
45         ANS=qpow(A,n);
46         printf("%lld
",(ANS.m[1][1]+ANS.m[2][1]+ANS.m[3][1])%RQY);
47     }
48 }

【洛谷P1939】 矩阵加速模板

【洛谷P1939】矩阵加速模板