Free tutorials to bookmark

First introduce the fast power of the number

, for example, calculate the 5 steps of 2, conventional algorithm 2*2*2*2*2, use the idea of fast power, find 5 binary expressions 101, the number of power on the weight of 1 and 4 is 1, 1 and 4 are 1, 1 and 4 are 1. That is 2^5 = 2^1*2^4. The code is as follows, the time complexity is O (logn)

#include<iostream>
using namespace std;
typedef long long ll;
const int mod=1000000007;
ll quick_pow(int n,int p)
{
    ll ans=1;
    ll m=n;
    while(p)
    {
        if(p%2) ans=(ans*m)%mod;
        m=(m*m)%mod;
        p>>=1;
    }
    return ans;
}
int main (void)
{
    int n,p;
    cin>>n>>p;
    cout<<quick_pow(n,p)<<endl;
    return 0;
}

matrix fast power: Optimize the high recursor efficiency, take soj 4454 as an example, N can reach 10^18, it is impossible to handle it one by one.

Delivery:

matrix multiplication time complexity is O (n^3), and the idea of fast power when seeking the power of the matrix can be transformed from O (n) to O (LOGN)

code is as follows: [Pay attention to mold

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int mod=1000000007;
const int N=3;
//a*f(x-1)+b*f(x-2)+c
int a,b,c;
ll f1,f2;
struct Matrix
{
    int row,cal;
    ll m[N][N];
    Matrix()
    {
        row=3,cal=3;
        m[0][0]=a,m[0][1]=1,m[0][2]=0;
        m[1][0]=b,m[1][1]=0,m[1][2]=0;
        m[2][0]=c,m[2][1]=0,m[2][2]=1;
    }
};
Matrix init(Matrix a,ll t)
{
    for(int i=0;i<a.row;i++)
        for(int j=0;j<a.cal;j++)
            a.m[i][j]=t;
    return a;
}
Matrix mul(Matrix a,Matrix b)
{
    Matrix ans;
    ans.row=a.row,ans.cal=b.cal;
    ans=init(ans,0);
    for(int i=0;i<a.row;i++)
        for(int j=0;j<b.cal;j++)
            for(int k=0;k<a.cal;k++)
                ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
    return ans;
}
Matrix add(Matrix a,Matrix b)
{
    Matrix ans;
    for(int i=0;i<a.row;i++)
        for(int j=0;j<a.cal;j++)
            ans.m[i][j]=(a.m[i][j]+b.m[i][j])%mod;
    return ans;
}
ll quick_pow(ll n)
{
    if(n==1) return f1;
    if(n==2) return f2;
    n-=2;
    Matrix ans,t;
    ans.row=1,ans.cal=3;
    ans.m[0][0]=f2,ans.m[0][1]=f1,ans.m[0][2]=1;
    while(n)
    {
        if(n%2) ans=mul(ans,t);
        t=mul(t,t);
        n>>=1;
    }
    return ans.m[0][0];
}
int main (void)
{
    ll n;
    f1=2,f2=2;
    a=1,b=3,c=1;
    while(cin>>n)
        cout<<quick_pow(n)<<endl;
    return 0;
}