本文写于2017-11-09，其中的一些思路和基础知识可能存在问题,公式也未用LATEX编写。本文移至此处时暂未重新学习。

    求递推数列的第N项，通常做法的复杂度大概是O(n)
    使用矩阵加速幂可以把复杂度降到O(log n)
    大体遇到的问题：

    1. 递推数列化为矩阵
    2. 矩阵乘法

    第一个问题，大概是这样的：
    矩阵加速幂求递推数列的项 - 图1

    第二个问题就是矩阵乘法啦！
    ~~

    1. //对于f[n]=∑a[i]*f[n-i] 
    2. #include<iostream>
    3. #include<cstdio>
    4. #include<algorithm>
    5. #include<cstring>
    7. using namespace std;
    9. struct sq{long long a[105][105];}base,mu,ans;
    11. void init(sq &_1){memset(_1.a,0,sizeof(_1.a));}
    13. int m,n;//m  公式中i取值的最大值（即f[n]与f[n-1]~f[n-m-1]直接相关）   n  所求的f[n] 
    14. long long mod;
    16. sq mul(sq _1,sq _2)//两个m*m的矩阵相乘
    17. {
    18.     sq ans;
    19.     init(ans);
    20.     for(int i=1;i<=n;i++)
    21.         for(int j=1;j<=n;j++)
    22.             for(int k=1;k<=n;k++)
    23.                 ans.a[i][j]+=_1.a[i][k]*_2.a[k][j]%mod,
    24.                 ans.a[i][j]%=mod;
    25.     return ans;
    26. } 
    28. sq spow(sq _1,long long k)
    29. {
    30.     sq base=_1,ans=_1;
    31.     k--;
    32.     while(k)
    33.     {
    34.         if(k&1)    ans=mul(ans,base);
    35.         base=mul(base,base);
    36.         k>>=1;
    37.     }
    38.     return ans;
    39. }
    41. sq amul(sq _1,sq _2)
    42. {
    43.     sq ans;
    44.     init(ans);
    45.     for(int i=1;i<=n;i++)
    46.         for(int j=1;j<=n;j++)
    47.             ans.a[1][i]+=_1.a[j][1]*_2.a[j][i]%mod,
    48.             ans.a[1][i]%=mod;
    49.     return ans;
    50. }
    52. void build_sq() 
    53. {
    54.     init(base);
    55.     for(int i=1;i<=m;i++)    cin>>base.a[1][i];//读入f[n-i]的系数a[i]
    56.     for(int j=1;j<m;j++)    base.a[j+1][j]=1; //把base矩阵建好 
    57.     for(int i=1;i<=m;i++)    cin>>mu.a[m-i+1][1];//读入f[1]~f[m] 
    58. }
    60. int main()
    61. {
    62.     ios::sync_with_stdio(false);
    63.     cin>>m>>n>>mod;
    64.     build_sq();//把矩阵存好！
    65.     sq ans=amul(mu,spow(base,n-m));
    66.     cout<<ans.a[1][1]<<endl;
    67.     return 0;
    68. }

    这个代码没有对应任何题，所以不知道对不对