洛谷P1939 矩阵快速幂模板

矩阵快速幂解线性递推式：

$$a_n=a_{n-1}+a_{n-3}$$

Solution：

一般构造矩阵的时候都构造一个连续的矩阵，且这个矩阵元素下标都$+1$后两个矩阵恰好覆盖了递推式所涉及的所有项，设递推式跨越的下标长度为$len$，这个长度一般是$len-1$，譬如当前构造矩阵
$$[a_n,a_{n-1},a_{n-2}]$$
我们需要构造出一个矩阵，使得这个上式矩阵乘构造矩阵后得到
$$[a_{n+1},a_n,a_{n-1}]$$

矩阵乘法：

对于两个矩阵$a,b$相乘，结果矩阵的$i$行$j$列为
$$\sum _{k=1}^n{a}_{i,k}{b}_{k,j}$$
即$a$的$i$行与$b$的$j$列的所有元素对应相乘相加

单位矩阵：

是主对角线元素为$1$，其余元素为$0$的矩阵，即满足下式的矩阵
a i , j = { 0 i ≠ j 1 i = j a_{i,j}=

{0i≠j1i=j" role="presentation" style="position: relative;">{01i≠ji=j$$\{\begin{array}{ll}0& i\ne j\\ 1& i=j\end{array}$$

ai,j​={01​i​=ji=j​

根据矩阵乘法的规则构造矩阵为
[ 1 1 0 0 0 1 1 0 0 ] \left[

\right] ⎣⎡​101​100​010​⎦⎤​
对此矩阵快速幂即可

需要注意的是，单位矩阵是主对角线元素为$1$的矩阵，其他元素为$0$；而不是都是$1$的矩阵

// #include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

using ll=long long;
const int N=1e6+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=1e9+7;

struct matrix
{
    ll a[3][3];
    void initial(){memset(a,0,sizeof(a));}
    void build()
    {
        initial();
        for(int i=0;i<3;i++) a[i][i]=1;
    }
    ll* operator[](int i) const {
        return (ll*)&a[i][0];
    }
    matrix operator*(const matrix& x) const
    {
        matrix ret; ret.initial();
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                for(int k=0;k<3;k++) ret[i][j]=(ret[i][j]+a[i][k]*x[k][j]%mod)%mod;
        return ret;
    }
};

matrix qpow(matrix a,ll b)
{
    matrix ret,base=a; ret.build();
    while(b)
    {
        if(b&1) ret=ret*base;
        base=base*base;
        b>>=1;
    }
    return ret;
}

int main()
{
    matrix tmp={{
        {1,1,0},
        {0,0,1},
        {1,0,0}
    }},ans={{
        {1,1,1},
        {0,0,0},
        {0,0,0}
    }};
    int t; cin>>t;
    while(t--)
    {
        ll n; cin>>n;
        if(n<=3) cout<<1<<'\n';
        else cout<<(ans*qpow(tmp,n-3)).a[0][0]<<'\n';
    }
    return 0;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69