# ListView GridView shielding and nesting method LPF

2023-01-23   ES

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

Reprinted: https://www.cnblogs.com/tuesdayzz/p/5758863.html

source