矩阵加速数列(学习笔记)

当我们遇到这样一类问题:已知递推式,但数据范围太大,直接递推下去肯定会超时,例如求斐波拉契数列的第n项(\(n<=10^{18}\))等等.这是我们就需要用到矩阵来加速递推,优化时间复杂度.

步骤和思想都很简单.以求斐波拉契数列的第n项为例.我们已知递推式\(f(n)=f(n-2)+f(n-1)\),把等式两边各抽象为一个矩阵,即我们已知\(S(n-1)=[f(n-1),f(n-2)]\),要求出\(S(n)=[f(n),f(n-1)]\),那么\(S(n-1)\)如何变换到\(S(n)\)呢?可以乘上转移矩阵\(T= [\begin{matrix} 1 & 1 \\1 & 0 \end{matrix}]\),这里可以自己根据矩阵乘法运算法则手玩出来.

于是就可以设出初始矩阵\(S(0)\),然后\(S(n)=S(0)*T^n\),显然\(T^n\)可以通过矩阵快速幂来求得.my题解

至于细节和实现直接结合模板题来看.我先说明一下,每个人的矩阵可能会有一些写法上的差别.

洛咕

题意:\(a[1]=a[2]=a[3]=1\);\(a[x]=a[x-3]+a[x-1] (x>3)\).求a数列的第n项对1e9+7取余的值.

分析:模板题.已知矩阵为\(S(n-1)=[f(n-1),f(n-2),f(n-3)]\),目标矩阵为\(S(n)=[f(n),f(n-1),f(n-2)]\),通过手玩可得转移矩阵\(T=[\begin{matrix} 1 & 1 & 0\\0 & 0 & 1\\1 & 0 & 0\end{matrix}]\).

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
const int mod=1e9+7;
struct matrix{//这是一个板子,重载了'*'
    int a[3][3];
    matrix operator *(matrix b){
    matrix c;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            c.a[i][j]=0;
//一定要记得初始化
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                c.a[i][j]=(c.a[i][j]+1LL*a[i][k]*b.a[k][j])%mod;
        return c;
    }
}S,T;
int main(){
    int Q=read();
    while(Q--){
        int n=read();
        if(n==1||n==2||n==3){
            puts("1");
            continue;
        }
        n-=3;
//因为题目给了我们前三项,我们的初始矩阵就用前三项
//所以我们需要特判前三项,特判通过之后n=n-3
        S.a[0][0]=1;S.a[0][1]=1;S.a[0][2]=1;
//构建出初始矩阵
        T.a[0][0]=1;T.a[0][1]=1;T.a[0][2]=0;
        T.a[1][0]=0;T.a[1][1]=0;T.a[1][2]=1;
        T.a[2][0]=1;T.a[2][1]=0;T.a[2][2]=0;
//构建出转移矩阵
        while(n){if(n&1)S=S*T;T=T*T;n>>=1;}
//快速幂
        printf("%d\n",S.a[0][0]);   
    }
    return 0;
}

洛咕

题意:求斐波那契数列的第n项.

分析:最开始那段文字已经写出来了.

const LL mod=1e9+7;
struct matrix{
    LL a[2][2];
    matrix operator *(matrix b){
        matrix c;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                c.a[i][j]=0;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                    c.a[i][j]=(c.a[i][j]+1LL*a[i][k]*b.a[k][j])%mod;
        return c;
    }
}S,T;
int main(){
    S.a[0][0]=1;S.a[0][1]=1;
    T.a[0][0]=1;T.a[0][1]=1;T.a[1][0]=1;T.a[1][1]=0;
    LL n=read();
    if(n==1||n==2){puts("1");return 0;}
    n-=2;
    while(n){if(n&1)S=S*T;T=T*T;n>>=1;}
    printf("%lld\n",S.a[0][0]%mod);
    return 0;
}

洛咕

题意:广义的斐波那契数列是指形如\(a_n=p\times a_{n-1}+q\times a_{n-2}\)的数列.给定数列的两系数\(p\)和\(q\)，以及数列的最前两项\(a_1\)和\(a_2\),另给出两个整数\(n\)和\(m\)，试求数列的第\(n\)项\(a_n\)除以\(m\)的余数.

分析:按照步骤列出已知矩阵\(S(n-1)=[f(n-1),f(n-2)]\),目标矩阵\(S(n)=[f(n),f(n-1)]\),手玩出转移矩阵\(T=[\begin{matrix} p & 1 \\q & 0 \end{matrix}]\).(有一个要注意的地方:初始矩阵中\(f(n-2)=a_1,f(n-1)=a_2\)).

LL p,q,a1,a2,n,m;
struct matrix{
    LL a[2][2];
    matrix operator *(matrix b){
        matrix c;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                c.a[i][j]=0;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                    c.a[i][j]=(c.a[i][j]+1LL*a[i][k]*b.a[k][j])%m;
        return c;
    }
}S,T;
int main(){
    p=read();q=read();a1=read();a2=read();n=read();m=read();
    if(n==1){printf("%lld\n",a1);return 0;}
    if(n==2){printf("%lld\n",a2);return 0;}
//本题貌似没有构造需要特判的数据
    n-=2;//n还是要-2
    S.a[0][0]=a2;S.a[0][1]=a1;
    T.a[0][0]=p;T.a[0][1]=1;
    T.a[1][0]=q;T.a[1][1]=0;
    while(n){if(n&1)S=S*T;T=T*T;n>>=1;}
    printf("%lld\n",S.a[0][0]%m);   
    return 0;
}

矩阵加速数列(学习笔记)

原文：https://www.cnblogs.com/PPXppx/p/10587909.html