矩阵快速幂求递推数列

递推思路：

斐波那契(Fibonacci)数列

从第三项开始，每一项都是前两项之和， $F_{n}$

$F_{n}$ $= {\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}}^{n - 1} \times {\begin{matrix} F_{1} \\ F_{0} \end{matrix}}$

$F_{n}$

关键是根据题中递推关系构造出底数矩阵！

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 using namespace std;
 5 typedef long long ll;
 6 const int maxn=3;
 7 const int mod=1e9+9;
 8 struct jz
 9 {
10     ll a[maxn][maxn];
11 }base,unit;   //底数矩阵，单位矩阵
12 
13 jz operator*(jz aa,jz bb)//重载函数*
14 {
15     jz c;
16     for(ll i=1;i<=maxn-1;i++)
17     {
18         for(ll j=1;j<=maxn-1;j++)
19         {
20             ll t=0;
21             for(ll k=1;k<=maxn-1;k++) t=(t%mod+aa.a[i][k]%mod*bb.a[k][j]%mod)%mod;
22             c.a[i][j]=t%mod;
23         }
24     }
25 
26     return c;
27 }
28 
29 jz ksm(jz base,ll b)
30 {
31     jz r=unit;
32     while(b)
33     {
34         if(b&1) r=r*base;
35         base=base*base;
36         b>>=1;
37     }
38 
39     return r;
40 }
41 
42 int main()
43 {
44     base.a[1][1]=1;base.a[1][2]=1;//初始化工作
45     base.a[2][1]=1;base.a[2][2]=0;
46     unit.a[1][1]=1;unit.a[2][2]=1;
47 
48     ll n;
49     cin>>n;
50     if(n==0) cout<<'0'<<endl;
51     else if(n==1) cout<<'1'<<endl;
52     else
53     {
54         jz ans=ksm(base,n-1);
55         //cout<<ans.a[1][1]<<endl; 写成这样也行,但最好写成下面便于理解的(不要省了)
56         cout<<ans.a[1][1]*1+ans.a[1][2]*0<<endl;
57     }
58 
59     return 0;
60 }

还有稍微延申的题洛谷P1939

分析和思路：

这道题主要难度就是构造底数矩阵，构造出来是3维的

Fn Fn=Fn-1*1+Fn-2*0+Fn-3*1

Fn-1 这是我们想要的目标矩阵 Fn-1=Fn-1*1+Fn-2*0+Fn-3*0 这是构造过程

Fn-2 Fn-2=Fn-1*0+Fn-2*1+Fn-3*0

1 0 0

0 1 1

那么这题就完了，套用快速幂公式即可

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 using namespace std;
 5 typedef long long ll;
 6 const int maxn=4;
 7 const int mod=1e9+7;
 8 struct jz
 9 {
10     ll a[maxn][maxn];
11 }base,unit;   //底数矩阵，单位矩阵
12 
13 jz operator*(jz aa,jz bb)//重载函数*
14 {
15     jz c;
16     for(ll i=1;i<=maxn-1;i++)
17     {
18         for(ll j=1;j<=maxn-1;j++)
19         {
20             ll t=0;
21             for(ll k=1;k<=maxn-1;k++) t=(t%mod+aa.a[i][k]%mod*bb.a[k][j]%mod)%mod;
22             c.a[i][j]=t%mod;
23         }
24     }
25 
26     return c;
27 }
28 
29 jz ksm(jz base,ll b)
30 {
31     jz r=unit;
32     while(b)
33     {
34         if(b&1) r=r*base;
35         base=base*base;
36         b>>=1;
37     }
38 
39     return r;
40 }
41 
42 int main()
43 {
44     base.a[1][1]=1;base.a[1][2]=0;base.a[1][3]=1;//初始化工作
45     base.a[2][1]=1;base.a[2][2]=0;base.a[2][3]=0;
46     base.a[3][1]=0;base.a[3][2]=1;unit.a[3][3]=0;
47 
48     unit.a[1][1]=1;unit.a[2][2]=1;unit.a[3][3]=1;
49 
50     int T;
51     cin>>T;
52     while(T--)
53     {
54         ll n;
55         cin>>n;
56         if(n==1 || n==2 || n==3) cout<<'1'<<endl;
57         else
58         {
59             jz ans=ksm(base,n-3);
60             cout<<(ans.a[1][1]*1+ans.a[1][2]*1+ans.a[1][3]*1)%mod<<endl;
61         }
62     }
63 
64     return 0;
65 }

类似题51nod1126

套路一样，但有几个注意地方！

注意：因为最开始已知2数为1,1,后面不是0，所以最终结果不是a[1][1]，而是a[1][1]+a[1][2]！！（即必须*一列初始已知条件）
还有//注意:从3开始,所以N-2次方(而斐波那从2开始刚好N-1次方),计算从第3项时运算了几次幂即可分清楚！

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 using namespace std;
 5 typedef long long ll;
 6 const int maxn=3;
 7 const int mod=7;
 8 int A,B,N;
 9 struct jz
10 {
11     ll a[maxn][maxn];
12 }base,unit;   //底数矩阵,单位矩阵
13 
14 jz operator*(jz aa,jz bb)//重载函数*
15 {
16     jz c;
17     for(ll i=1;i<=maxn-1;i++)
18     {
19         for(ll j=1;j<=maxn-1;j++)
20         {
21             ll t=0;
22             for(ll k=1;k<=maxn-1;k++)
23             {
24                 t=(t+aa.a[i][k]*bb.a[k][j])%mod;
25                 t=(t+mod)%mod;
26             }
27             c.a[i][j]=t%mod;
28         }
29     }
30 
31     return c;
32 }
33 
34 jz ksm(jz base,ll b)
35 {
36     jz r=unit;
37     while(b)
38     {
39         if(b&1) r=r*base;
40         base=base*base;
41         b>>=1;
42     }
43 
44     return r;
45 }
46 
47 int main()
48 {
49     cin>>A>>B>>N;
50     base.a[1][1]=A;base.a[1][2]=B;//初始化工作
51     base.a[2][1]=1;base.a[2][2]=0;
52     unit.a[1][1]=1;unit.a[2][2]=1;
53 
54     if(N==1 || N==2) cout<<'1'<<endl;
55     else
56     {
57         jz ans=ksm(base,N-2);
58         cout<<(ans.a[1][1]*1+ans.a[1][2]*1)%mod<<endl;
59     }
60 
61     return 0;
62 }

到这应该是最终麻烦的终极版本了吧：

和51nod1126相乘相同的一道题，只不过递推项更多，递推难度加大，更注重精确地考察了矩阵快速幂几点规律

If x < 10： f(x) = x.

If x >= 10 ：f(x) = a0 f(x-1) + a1 f(x-2) + a2 f(x-3) + …… + a9 f(x-10);

ai(0<=i<=9) 只能是0或者1

现在求 f(n)%mod 的值

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <iomanip>
 5 #include <cstdio>
 6 #include <cstring>
 7 #include <cmath>
 8 using namespace std;
 9 typedef long long llo;
10 typedef unsigned long long ull;
11 const int maxn=11;
12 llo n;
13 int mod;
14 int A[11];
15 struct jz
16 {
17     llo a[maxn][maxn];
18 }base,unit;   //底数矩阵，单位矩阵
19 jz operator *(jz aa,jz bb)
20 {
21     jz c;
22     for(llo i=1;i<=maxn-1;i++)
23     {
24         for(llo j=1;j<=maxn-1;j++)
25         {
26             llo t=0;
27             for(llo k=1;k<=maxn-1;k++) t=(t%mod+aa.a[i][k]%mod*bb.a[k][j]%mod)%mod;
28             c.a[i][j]=t%mod;
29         }
30     }
31 
32     return c;
33 }
34 
35 jz ksm(jz base,llo b)
36 {
37     jz r=unit;
38     while(b)
39     {
40         if(b&1) r=r*base;
41         base=base*base;
42         b>>=1;
43     }
44 
45     return r;
46 }
47 
48 void Init()
49 {
50     base.a[1][1]=A[1];base.a[1][2]=A[2];base.a[1][3]=A[3];
51     base.a[1][4]=A[4];base.a[1][5]=A[5];base.a[1][6]=A[6];
52     base.a[1][7]=A[7];base.a[1][8]=A[8];base.a[1][9]=A[9];base.a[1][10]=A[10];//1.(列到x-10!)*的是系数放在第一行,放完共10列(这里是正着*!!)
53     base.a[2][1]=1;base.a[3][2]=1;base.a[4][3]=1;//(行到x-9列到x-9)下面行的系数好说基本都是每行一个1,放完9行(+第一行也是10行)
54     base.a[5][4]=1;base.a[6][5]=1;base.a[7][6]=1;
55     base.a[8][7]=1;base.a[9][8]=1;base.a[10][9]=1;
56 
57     unit.a[1][1]=1;unit.a[2][2]=1;unit.a[3][3]=1;//单位矩阵初始化很简单
58     unit.a[4][4]=1;unit.a[5][5]=1;unit.a[6][6]=1;
59     unit.a[7][7]=1;unit.a[8][8]=1;unit.a[9][9]=1;unit.a[10][10]=1;
60 
61 }
62 
63 
64 int main()
65 {
66     while(cin>>n>>mod)
67     {
68         for(int i=1;i<=10;i++) cin>>A[i];
69         Init();
70                              //3.n-9次幂从第几项开始推,试试这项运算了几次(如f(10)就运算了一次，所以一次幂直接*放好的底数矩阵就行!)
71         jz ans=ksm(base,n-9);//2.注意:最后*的是已知初始序列值(系数已经*过了),不是系数,开始一直错~~~因为最后是x-1,x-2...x-9往下排,所以值是反着*!
72         cout<<(ans.a[1][1]*9+ans.a[1][2]*8+ans.a[1][3]*7+ans.a[1][4]*6+ans.a[1][5]*5+ans.a[1][6]*4+ans.a[1][7]*3+ans.a[1][8]*2+ans.a[1][9]*1+ans.a[1][10]*0)%mod<<endl;
73     }
74 
75     return 0;
76 }

完。