矩阵加速

· · 个人记录

1.矩阵快速幂

友链

在学习矩阵加速递推之前，您先学一下矩阵快速幂。

(下面我默认您会矩阵快速幂了)

2.矩阵加速

2.1 例题

戳我

这个题目看题面就知道是一个递推。

然而我们看了一下数据范围：

这么大的吗 …… 然而我们就不能用 O(n) 如果您用了，TLE TLE TLE。

然后我们就要利用 矩阵快速幂 来加速。

那么 …… 怎么加速呢？我也不会呀。。。

2.2 构建系数矩阵

利用题面的递推式可以发现。

a_{i+1}=a_i+a_{i-2} a_i=a_{i-1} a_{i-1}=a_{i-2}

(i \leq 4)

根据这个，我们简单地构建出了系数矩阵。

\begin{bmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{bmatrix} 那么你可以试着用矩阵乘法左乘 $T$ 。 那么假如是：

\begin{bmatrix} 1 & 0 & 1 \ 1 & 0 & 0 \ 0 & 1 & 0 \ \end{bmatrix} \times \begin{bmatrix} 1 \ 1 \ 1 \ \end{bmatrix}

左乘一下你会发现，变成了：

\begin{bmatrix} 2 \ 1 \ 1 \ \end{bmatrix}

那么就是说：

T \times \begin{bmatrix} ai \ a{i-1} \ a{i-2} \ \end{bmatrix}= \begin{bmatrix} a{i+1} \ a{i} \ a{i-1} \ \end{bmatrix}

这样子就矩阵整体移动了一位。 ### 2.3 加速递推 然后就会有人问："这个不是矩阵乘法吗？如果这样算的话，那么不就和 $O(n)$ 差不多了吗？" 对呀，单独这样算下来肯定是和 $O(n)$ 一样呀。(除非你有玄学的卡常技巧) 那么怎么办呢？ 如果说左乘一个 $T$ 就会让整个矩阵向前移动一位。 那么 …… 左乘 $n$ 个 $T$ 就会让矩阵向前移动 $n$ 位。 然后 $T^n \times \begin{bmatrix} a_{1} \\ a_{0} \\ a_{-1} \\ \end{bmatrix}$ (矩阵乘法满足乘法结合律) 那么就会得出：

\begin{bmatrix} a{n+1} \ a{n} \ a_{n-1} \ \end{bmatrix}

那么 …… 这样子看来，$T^n$ 不就可以利用 矩阵快速幂 加速了吗？ 然后再乘一下

\begin{bmatrix} a{1} \ a{0} \ a_{-1} \ \end{bmatrix}

也就是这个题目中的

\begin{bmatrix} 1 \ 0 \ 0 \ \end{bmatrix}$ 矩阵。

就可以了。

那么就可以达到 O(\log n) 的效率了！

2.4 代码

其实我觉得，你思路理解了之后代码就更本不用看了。。。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int Mod=1e9+7;
const int INF=5;
struct _node {
        long long a[INF][INF];
} ans,b;
int t,n;
inline void init()
{
        n=0;
        scanf("%d",&n);
        memset(ans.a,0,sizeof(ans.a));
        for (int i=1; i<=3; i++) ans.a[i][i]=1;
        memset(b.a,0,sizeof(b.a));
        b.a[1][1]=1; b.a[1][3]=1;
        b.a[2][1]=1;
        b.a[3][2]=1;
}
//初始化。
inline _node mul(_node x,_node y)
{
        _node z;
        memset(z.a,0,sizeof(z.a));
        for (int i=1; i<=3; i++)
                for (int j=1; j<=3; j++)
                        for (int k=1; k<=3; k++)
                                z.a[i][j]=(z.a[i][j]%Mod+(x.a[i][k]%Mod*y.a[k][j]%Mod))%Mod;
        return z;
}
//矩阵乘法。
inline int pow_ksm()
{
        // n-=3;
        while (n) {
                if (n&1) ans=mul(ans,b);
                b=mul(b,b);
                n>>=1;
        }
        return ans.a[2][1]%Mod;
        //然后矩阵快速幂，至于为什么要取 ans.a[2][1] 自己在看一下前面的。
}
signed main()
{
        scanf("%d",&t);
        for (int i=1; i<=t; i++)
        {
                init();
                if (n<=3) {
                        printf("1\n");
                        continue;
                        //如果是 <=3 的那么直接输出 1。
                }
                printf("%d\n",pow_ksm());
                //如果是 >=4 那么输出矩阵快速幂的结果。
        }
        return 0;
}
\operatorname{updata}:2020/4/7

然后学完这些矩阵，就可以做斐波那契数列加速了。

戳我

3.斐波那契数列

那么这个斐波那契数列怎么加速呢？

一步一步来推。

3.1 初始矩阵

那么继续来构建一个初始矩阵。

根据递推公式：

f_i=f_{i-1}+f_{i-2} f_{i-1}=f_{i-2} f_{i-2}=f_{i-3}

构建出了下面的矩阵：

\begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}

然后

\begin{bmatrix} 1 \\ 0 \\ \end{bmatrix}

就是最后要乘的矩阵相当于

\begin{bmatrix} a_1 \\ a_0 \\ \end{bmatrix}

那么乘上 T^n 就会变成

\begin{bmatrix} a_{n+1} \\ a_n \\ \end{bmatrix}

然后取 ans_{2,1} 的值就可以了。

还有就是 不开long long 见祖宗。

3.2 代码(核心)

__inline__ void init()
{
        for (int i=1; i<=2; i++) ans.a[i][i]=1;
        b.a[1][1]=b.a[1][2]=b.a[2][1]=1;
        //初始化。
}
__inline__ _node_k mul(_node_k x,_node_k y) {
        _node_k z;
        memset(z.a,0,sizeof(z.a));
        for (int i=1; i<=2; i++)
                for (int j=1; j<=2; j++)
                        for (int k=1; k<=2; k++)
                                z.a[i][j]=(z.a[i][j]+(x.a[i][k]*y.a[k][j])%Mod)%Mod;
        return z;
}
__inline__ long long pow_ksm()
{
        while (n>0) {
                if (n&1) ans=mul(ans,b);
                b=mul(b,b);
                n>>=1;
        }
        return ans.a[2][1]%Mod;
}

写在后面的话

我这篇题解如果有错误，那么请在评论区里留言，我将会很感谢反映的人。

谢谢观赏！