专栏文章

11.23倍增 / st表 / 矩阵乘法

ssunpeilun
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqyhhht
此快照首次捕获于
2025/12/04 12:48
3 个月前
此快照最后确认于
2025/12/04 12:48
3 个月前
查看原文
T1
一道快速幂的模板。
首先，一般计算aba^b的方法是不断地∗a\ast a，时间复杂度O(n),面对达到10910^9以上的数据就会超时，考虑O(logn)的算法。
快速幂的思想是把b拆分成2n2^n的形式，每一次取它的一个二进制位，如果是1，就将22位数2^{2^{位数}}乘进答案中,否则就跳过。
例如b为2152^{15},则b可以被拆成215=28+24+22+212^{15}=2^8+2^4+2^2+2^1；若b为2112^{11}，则b可以被拆成211=28+22+212^{11}=2^8+2^2+2^1。
Code:
CPP
#include<iostream>
using namespace std;
long long ksm(long long a,long long b,long long m){
    long long res=1,tmp=a;
    while(b){
        if(b%2==1) res=res%m*tmp%m;
        tmp=tmp*tmp%m;
        b/=2;
    }
    return res;
}
int main(){
    long long a,b,mod,ans;
    cin>>a>>b>>mod;
    ans=ksm(a,b,mod);
    cout<<a<<"^"<<b<<" mod "<<mod<<"="<<ans;
    return 0;
}
T5
一样是一道快速幂的模板题，不过加了矩阵。
矩阵乘法已经在题目中讲过并给出公式，不再赘述。
矩阵快速幂其实就是把快速幂中乘号对应的两个对象换成了矩阵而已，只需要专门定义一个函数（或重载乘号）来计算矩阵乘法就行了。
Code:
CPP
#include<iostream>
using namespace std;
long long n,k,ans[101][101],t[101][101],mod=1e9+7;
inline void jzc(bool f){
    long long fl[101][101]={};
    if(f){
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    fl[i][j]=(fl[i][j]%mod+t[i][k]%mod*t[k][j]%mod)%mod;
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++) t[i][j]=fl[i][j];
        }
    }else{
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    fl[i][j]=(fl[i][j]%mod+ans[i][k]%mod*t[k][j]%mod)%mod;
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++) ans[i][j]=fl[i][j];
        }
    }
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) cin>>t[i][j];
    }
    for(int i=1;i<=n;i++) ans[i][i]=1;
    while(k){
        if(k&1) jzc(0);
        jzc(1);
        k>>=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) printf("%lld ",ans[i][j]%mod);
        putchar('\n');
    }
    return 0;
}
T6
n开到2632^{63}，递推会TLE，考虑O(log n)的算法。
一样运用快速幂的思路，将斐波那契的计算过程转化成矩阵快速幂。
首先，我们已知Fib(n)=Fib(n−1)+Fib(n−2)Fib(n)=Fib(n-1)+Fib(n-2)，把它写成矩阵乘法的形式即为：[Fib(n)Fib(n−1)]=[1110]∗[Fib(n−1)Fib(n−2)]\begin{bmatrix} Fib(n) \\ Fib(n-1) \end{bmatrix}=\begin{bmatrix} 1 & 1\\ 1& 0\end{bmatrix}\ast\begin{bmatrix} Fib(n-1) \\ Fib(n-2) \end{bmatrix}
像这样推下去，我们会得到： [Fib(n)Fib(n−1)]=[1110]n−2∗[Fib(1)Fib(2)]\begin{bmatrix} Fib(n) \\ Fib(n-1) \end{bmatrix}=\begin{bmatrix} 1 & 1\\ 1& 0\end{bmatrix}^{n-2}\ast\begin{bmatrix} Fib(1) \\ Fib(2) \end{bmatrix}
已知Fib(1)=Fib(2)=1Fib(1)=Fib(2)=1，这就变成了一道矩阵快速幂。
Code:
CPP
#include<iostream>
using namespace std;
long long n,s,ans[3][3],t[3][3],mod=1e9+7;
inline void jzc(bool f){
    long long fl[3][3]={};
    if(f){
        for(int k=1;k<=2;k++){
            for(int i=1;i<=2;i++){
                for(int j=1;j<=2;j++){
                    fl[i][j]=(fl[i][j]%mod+t[i][k]%mod*t[k][j]%mod)%mod;
                }
            }
        }
        for(int i=1;i<=2;i++){
            for(int j=1;j<=2;j++) t[i][j]=fl[i][j];
        }
    }else{
        for(int k=1;k<=2;k++){
            for(int i=1;i<=2;i++){
                for(int j=1;j<=2;j++){
                    fl[i][j]=(fl[i][j]%mod+ans[i][k]%mod*t[k][j]%mod)%mod;
                }
            }
        }
        for(int i=1;i<=2;i++){
            for(int j=1;j<=2;j++) ans[i][j]=fl[i][j];
        }
    }
}
int main(){
    cin>>n;
    if(n<=2){
        cout<<1;
        return 0;
    }
    s=n-2;
    ans[1][1]=1;
    ans[1][2]=1;
    t[1][1]=1;
    t[1][2]=1;
    t[2][1]=1;
    while(s){
        if(s&1) jzc(0);
        jzc(1);
        s>>=1;
    }
    cout<<ans[1][1];
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...