11.23倍增 / st表 / 矩阵乘法

· · 个人记录

T1
一道快速幂的模板。
首先，一般计算a^b的方法是不断地\ast a，时间复杂度O(n),面对达到10^9以上的数据就会超时，考虑O(logn)的算法。

快速幂的思想是把b拆分成2^n的形式，每一次取它的一个二进制位，如果是1，就将2^{2^{位数}}乘进答案中,否则就跳过。

例如b为2^{15},则b可以被拆成2^{15}=2^8+2^4+2^2+2^1；若b为2^{11}，则b可以被拆成2^{11}=2^8+2^2+2^1。
Code:

#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:

#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开到2^{63}，递推会TLE，考虑O(log n)的算法。
一样运用快速幂的思路，将斐波那契的计算过程转化成矩阵快速幂。

首先，我们已知Fib(n)=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}
像这样推下去，我们会得到：

\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)=1，这就变成了一道矩阵快速幂。
Code:

#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;
}