线性递推公式找递推矩阵的方法：

https://blog.csdn.net/synapse7/article/details/18790165

构造方法：规定由递推矩阵A，左乘由项构成的矩阵F，其中矩阵A的第一列为对应系数，左下角为单位矩阵，右下角为零矩阵。

对于递推式的常数C，在矩阵F中增加最后一行C，在A的最右列增加两个1（通常选右上角和左下角）。

对于递推式的C的n次方，在矩阵F中增加最后一行C的n次方，在A的最右列增加两个C（通常选右上角和左下角）。

 

以斐波那契数列为例，这里使用了快速乘进一步防止溢出。

#include
     
      using namespace std;#define ll long long#define MAXN 2ll mod=1000000007;//快速乘 a*b%p 防止乘法溢出llll qmut(ll a,ll b){    ll res=0;    while(b){        if(b&1) res=(res+a)%mod;        a=(a+a)%mod;        b>>=1;    }    return res;}class Matrix {  public:    ll m[MAXN][MAXN];    //二维数组存放矩阵    Matrix() {        memset(m,0,sizeof(m));    }    //对数组的初始化    void init(ll num[MAXN][MAXN]) {        for(int i = 0 ; i < MAXN ; i++) {            for(int j = 0 ; j < MAXN ; j++) {                m[i][j] = num[i][j];            }        }    }    Matrix operator*(Matrix &m1) {        int i, j, k;        Matrix t;        for(i = 0; i < MAXN; i++) {            for(j = 0; j < MAXN; j++) {                t.m[i][j] = 0;                for(k = 0 ; k < MAXN ; k++)                    t.m[i][j] = (t.m[i][j] + qmut(m[i][k],m1.m[k][j]))%mod;            }        }        return t;    }    Matrix qpow(ll n) {        Matrix t;        for(int i = 0 ; i < MAXN ; i++)            for(int j = 0 ; j < MAXN ; j++)                t.m[i][j] = (i == j);        Matrix M=*this;        while(n) {            if(n & 1)                t = t * M;            n = n >> 1;            M = M * M;        }        return t;    }    void show() {        for(int i=0; i
      
       >n;    if(n<=2){        cout<<1<
      
     

 

https://www.luogu.org/problemnew/show/P1939

 

#include
     
      using namespace std;#define ll long long#define MAXN 4ll mod=1000000007;//快速乘 a*b%p 防止乘法溢出llll qmut(ll a,ll b){    ll res=0;    while(b){        if(b&1) res=(res+a)%mod;        a=(a+a)%mod;        b>>=1;    }    return res;}class Matrix {  public:    ll m[MAXN][MAXN];    //二维数组存放矩阵    Matrix() {        memset(m,0,sizeof(m));    }    //对数组的初始化    void init(ll num[MAXN][MAXN]) {        for(int i = 0 ; i < MAXN ; i++) {            for(int j = 0 ; j < MAXN ; j++) {                m[i][j] = num[i][j];            }        }    }    Matrix operator*(Matrix &m1) {        int i, j, k;        Matrix t;        for(i = 0; i < MAXN; i++) {            for(j = 0; j < MAXN; j++) {                t.m[i][j] = 0;                for(k = 0 ; k < MAXN ; k++)                    t.m[i][j] = (t.m[i][j] + qmut(m[i][k],m1.m[k][j]))%mod;            }        }        return t;    }    Matrix qpow(ll n) {        Matrix t;        for(int i = 0 ; i < MAXN ; i++)            for(int j = 0 ; j < MAXN ; j++)                t.m[i][j] = (i == j);        Matrix M=*this;        while(n) {            if(n & 1)                t = t * M;            n = n >> 1;            M = M * M;        }        return t;    }    void show() {        for(int i=0; i
     

 

---

 

带n的次方的矩阵快速幂，找出相邻两项的关系就可以，用杨辉三角就可以了。

#include
     
      using namespace std;#define ll long long#define MAXN 8ll mod=2147493647;class Matrix {  public:    ll m[MAXN][MAXN];    //二维数组存放矩阵    Matrix() {        memset(m,0,sizeof(m));    }    //对数组的初始化    void init(ll num[MAXN][MAXN]) {        for(int i = 0 ; i < MAXN ; i++) {            for(int j = 0 ; j < MAXN ; j++) {                m[i][j] = num[i][j];            }        }    }    Matrix operator*(Matrix &m1) {        int i, j, k;        Matrix t;        for(i = 0; i < MAXN; i++) {            for(j = 0; j < MAXN; j++) {                t.m[i][j] = 0;                for(k = 0 ; k < MAXN ; k++)                    t.m[i][j] = (t.m[i][j] + m[i][k]*m1.m[k][j]%mod)%mod;            }        }        return t;    }    Matrix qpow(ll n) {        Matrix t;        for(int i = 0 ; i < MAXN ; i++)            for(int j = 0 ; j < MAXN ; j++)                t.m[i][j] = (i == j);        Matrix M=*this;        while(n) {            if(n & 1)                t = t * M;            n = n >> 1;            M = M * M;        }        return t;    }    void show() {        for(int i=0; i