题解：P2544 [AHOI2004] 数字迷阵

Thekhoi_ · 2024-08-24 15:11:23 · 题解

题目传送门

P2544 [AHOI2004] 数字迷阵=矩阵乘法&快速幂+斐波那契数列基础知识

１.斐波那契数列

分析题意，已知：

每一行都是斐波那契数列。

需要求的是：

第 i 行第 j 列的数。

容易得出：

只需要求出第 i 行第一个数，然后根据斐波那契数列的递推公式，就可以求出第 i 行第 j 列的数。

如何求出第 i 行第一个数：

将每一行第一个数两两相减，整理之后将差值排列：

发现是斐波那契数列变形，因而推出公式：
t\gets(1+\sqrt{5})/2， f1\gets(n\times t+n-1)， f2\gets(2\times f1-n+1)

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double t=1.0*(1+sqrt(5))/2; 
int n,m,Mod,f,f1,f2;
int main(){
    cin>>n>>m>>Mod;
    f1=((ll)(n*t+n-1))%Mod;
    f2=((2*f1-n+1)%Mod+Mod)%Mod;
    if(m<=2){
        if(m==1) cout<<f1;
        if(m==2) cout<<f2;
        return 0;
    }
    for(int i=3;i<=m;i++){
        f=f1+f2,f1=f2,f2=f;//斐波那契递推公式
        while(f>Mod) f-=Mod;
        while(f1>Mod) f1-=Mod;
        while(f2>Mod) f2-=Mod;
    }
    while(f>Mod) f-=Mod;
    cout<<(ll)(f);
    return 0;
}

记录详情

几经思索发现发现正解是用快速幂优化。

２.快速幂

快速幂可以以 O(\log{n}) 的时间复杂度计算乘方。
主要思想就是把 a^b 中的次数 b 拆解成二进制数。

快速幂代码：

int qpow(int x,int y){
    int res=1;
    for(;y;y>>=1,x=1ll*x*x%Mod)
        if(y&1) res=res*x;
    return res;
}

３.矩阵乘法

矩阵乘法中第一个矩阵的列要等于第二个矩阵的行。
两个大小分别为 m\times n 和 n\times p 的矩阵 , 相乘的结果为一个大小为 m\times p 的矩阵。
通常将结果矩阵记作 C，有：
单位矩阵，除了对角线为 1，其他位置为 0 的矩阵。

任何矩阵乘上它的结果都是原矩阵。

矩阵乘法代码：

struct Matrix{
    int a[N][N];
    void clear(){memset(a,0,sizeof a);}
    void init(){for(int i=1;i<=n;i++) a[i][i]=1;}
    //单位矩阵 
};
Matrix operator*(const Matrix &a,const Matrix &b){
    Matrix c;c.clear();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                c.a[i][j]=(c.a[i][j]+(a.a[i][k]*b.a[k][j])%mod)%mod;
    return c;
} 
inline Matrix qpow(Matrix x,int y){
    Matrix res;res.clear(),res.init();
    for(;y;y>>=1,x=x*x)
        if(y&1) res=res*x;
    return res; 
}

模板题：矩阵加速（数列）建议搭配食用。

代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=3;
const double t=1.0*(1+sqrt(5))/2;
int Mod;
struct Matrix{
    int a[N][N];
    void clear(){memset(a,0,sizeof a);}
    void init(){for(int i=1;i<N;i++) a[i][i]=1;}
}x,res;
Matrix operator*(const Matrix &a,const Matrix &b){
    Matrix c;c.clear();
    for(int i=1;i<N;i++)
        for(int j=1;j<N;j++)
            for(int k=1;k<N;k++)
                c.a[i][j]=(c.a[i][j]+(ll)(a.a[i][k]*b.a[k][j])%Mod)%Mod;
    return c;
} 
inline void qpow(Matrix x,int y){
    res.clear(),res.init();
    for(;y;y>>=1,x=x*x)
        if(y&1) res=res*x;
}
int n,m,f1,f2;
int main(){
    cin>>n>>m>>Mod;
    f1=((ll)(n*t+n-1))%Mod;
    f2=((2*f1-n+1)%Mod+Mod)%Mod;
    if(m<=2){
        if(m==1) cout<<f1;
        if(m==2) cout<<f2;
        return 0;
    }
    x.a[1][1]=1,x.a[1][2]=1,x.a[2][1]=1;//常规转移矩阵 
    qpow(x,m-1);//快速幂 
    printf("%lld",((ll)f1*res.a[2][2]+(ll)f2*res.a[2][1])%Mod);
    return 0;
}