P3390 【模板】矩阵快速幂
早期代码忘记搬了
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define ri register int
using namespace std;
const int MOD=1e9+7;
ll n,k;
struct Matrix
{
ll a[105][105];
Matrix() {memset(a,0,sizeof(a));}
il void build(){for(ri i=1;i<=n;++i)a[i][i]=1;}//单位矩阵
};
Matrix operator *(const Matrix &x,const Matrix &y)
{
Matrix z;
for(ri k=1;k<=n;++k)
for(ri i=1;i<=n;++i)
for(ri j=1;j<=n;++j)
z.a[i][j]+=x.a[i][k]*y.a[k][j]%MOD,z.a[i][j]%=MOD;
return z;
}
il ll read()
{
ll as=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
while(ch>='0'&&ch<='9') as=(as<<3)+(as<<1)+(ch^48),ch=getchar();
return as*f;
}
il Matrix FPower(Matrix bs,ll pw)
{
Matrix ans; ans.build();
while(pw>0)
{
if(pw&1) ans=ans*bs;
pw>>=1,bs=bs*bs;
}
return ans;
}
int main()
{
n=read(),k=read();
Matrix a;
for(ri i=1;i<=n;++i)
for(ri j=1;j<=n;++j)
a.a[i][j]=read();
a=FPower(a,k);
for(ri i=1;i<=n;++i){
for(ri j=1;j<=n;++j)
printf("%d ",a.a[i][j]);
putchar('\n');
}
return 0;
}
T1 P1962 斐波那契数列
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define il inline
#define ri register int
using namespace std;
const int MOD=1e9+7;
int n;
struct Matrix{
int a[3][3];
Matrix(){memset(a,0,sizeof(a));}
il void build(){a[1][1]=a[2][2]=1;}
il void abuild(){a[1][1]=a[1][2]=1;}
}s;
il int gcd(int a,int b) {return a%b==0?b:gcd(b,a%b);}
il Matrix mul(Matrix a,Matrix b,bool f)
{
Matrix as;
for(ri k=1;k<=2;++k)
for(ri i=1;i<=(f?1:2);++i)
for(ri j=1;j<=2;++j)
as.a[i][j]+=(a.a[i][k]*b.a[k][j])%MOD,as.a[i][j]%=MOD;
return as;
}
il Matrix FastPower(Matrix base,int power)
{
Matrix as;as.build();
while(power>0)
{
if(power&1) as=mul(as,base,0);
power>>=1,base=mul(base,base,0);
}
return as;
}
signed main()
{
scanf("%lld",&n);
if(n<=2) printf("1");
else
{
Matrix a,b;//a构造 b答案
b.abuild(),a.a[1][2]=a.a[2][2]=a.a[2][1]=1;
a=FastPower(a,n-1),b=mul(b,a,1);
printf("%lld",b.a[1][1]%MOD);
}
return 0;
}
T2 P1349 广义斐波那契数列
点击查看代码
#include<bits/stdc++.h>
#define int long long //不开long long____
#define il inline
#define ri register int
using namespace std;
const int MOD=1e8;
int n,m;
struct Matrix{
int a[3][3];
Matrix(){memset(a,0,sizeof(a));}
il void build(){a[1][1]=a[2][2]=1;}
il void abuild(){a[1][1]=a[1][2]=1;}
}s;
il int gcd(int a,int b) {return a%b==0?b:gcd(b,a%b);}
il Matrix mul(Matrix a,Matrix b,bool f)
{
Matrix as;
for(ri k=1;k<=2;++k)
for(ri i=1;i<=(f?1:2);++i)
for(ri j=1;j<=2;++j)
as.a[i][j]+=(a.a[i][k]*b.a[k][j])%MOD,as.a[i][j]%=MOD;
return as;
}
il Matrix FastPower(Matrix base,int power)
{
Matrix as;as.build();
while(power>0)
{
if(power&1) as=mul(as,base,0);
power>>=1,base=mul(base,base,0);
}
return as;
}
signed main()
{
scanf("%d%d",&n,&m);
int id=gcd(n,m);
if(id<=2) printf("1");
else
{
Matrix a,b;//a构造 b答案
b.abuild(),a.a[1][2]=a.a[2][2]=a.a[2][1]=1;
a=FastPower(a,id-1),b=mul(b,a,1);
printf("%d",b.a[1][1]%MOD);
}
return 0;
}
T3 P1306 斐波那契公约数
点击查看代码
#include<bits/stdc++.h>
#define int long long //不开long long____
#define il inline
#define ri register int
using namespace std;
const int MOD=1e8;
int n,m;
struct Matrix{
int a[3][3];
Matrix(){memset(a,0,sizeof(a));}
il void build(){a[1][1]=a[2][2]=1;}
il void abuild(){a[1][1]=a[1][2]=1;}
}s;
il int gcd(int a,int b) {return a%b==0?b:gcd(b,a%b);}
il Matrix mul(Matrix a,Matrix b,bool f)
{
Matrix as;
for(ri k=1;k<=2;++k)
for(ri i=1;i<=(f?1:2);++i)
for(ri j=1;j<=2;++j)
as.a[i][j]+=(a.a[i][k]*b.a[k][j])%MOD,as.a[i][j]%=MOD;
return as;
}
il Matrix FastPower(Matrix base,int power)
{
Matrix as;as.build();
while(power>0)
{
if(power&1) as=mul(as,base,0);
power>>=1,base=mul(base,base,0);
}
return as;
}
signed main()
{
scanf("%d%d",&n,&m);
int id=gcd(n,m);
if(id<=2) printf("1");
else
{
Matrix a,b;//a构造 b答案
b.abuild(),a.a[1][2]=a.a[2][2]=a.a[2][1]=1;
a=FastPower(a,id-1),b=mul(b,a,1);
printf("%d",b.a[1][1]%MOD);
}
return 0;
}
T4 P1939 【模板】矩阵加速(数列)
点击查看代码
#include<bits/stdc++.h>
#define il inline
#define int long long
#define ri register int
#define ru register unsigned int
using namespace std;
const int MOD=1e9+7;
il int read()
{
int as=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
while(ch>='0'&&ch<='9') as=(as<<3)+(as<<1)+(ch^48),ch=getchar();
return as*f;
}
struct Matrix{
int a[5][5];
Matrix(){memset(a,0,sizeof(a));}
il void build() {a[1][1]=a[2][2]=a[3][3]=1;}
il void abuild() {a[1][1]=a[1][2]=a[1][3]=1;}
};
il Matrix mul(Matrix a,Matrix b,bool f)
{
Matrix as;
for(ri k=1;k<=3;++k)
for(ri i=1;i<=(f?1:3);++i)
for(ri j=1;j<=3;++j)
as.a[i][j]+=(a.a[i][k]*b.a[k][j])%MOD,as.a[i][j]%=MOD;
return as;
}
il Matrix FastPower(Matrix base,int power)
{
Matrix rt; rt.build();
while(power>0)
{
if(power&1) rt=mul(rt,base,0);
power>>=1,base=mul(base,base,0);
}
return rt;
}
signed main()
{
int T=read();
for(ri t=1,n;t<=T;++t)
{
Matrix b,ans; n=read(),ans.abuild();//b构造 ans答案
if(n<=3) {printf("1"),putchar('\n');continue;}
b.a[1][1]=b.a[1][2]=b.a[2][3]=b.a[3][1]=1;
b=FastPower(b,n-3);
ans=mul(ans,b,1),
printf("%d",ans.a[1][1]),putchar('\n');
}
return 0;
}
T5 P2044 [NOI2012] 随机数生成器
点击查看代码
#include<bits/stdc++.h>
#define int __int128
#define il inline
#define ri register int
#define ru register unsigned int
using namespace std;
int m,a,c,x0,n,g;
struct Matrix{
int a[3][3];
Matrix(){memset(a,0,sizeof(a));}
il void build(){a[1][1]=a[2][2]=1;}
};
il int read()
{
int as=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar();
while(ch>='0'&&ch<='9') as=(as<<3)+(as<<1)+(ch^48),ch=getchar();
return as*f;
}
il void write(int x)
{
if(x==0) return;
char ch=x%10+'0';
write(x/10),putchar(ch);
}
il Matrix mul(Matrix x,Matrix y,bool f)
{
Matrix rt;
for(ru k=1;k<=2;++k)
for(ru i=1;i<=(f?1:2);++i)
for(ru j=1;j<=2;++j)
rt.a[i][j]+=(x.a[i][k]*y.a[k][j])%m,rt.a[i][j]%=m;
return rt;
}
il Matrix FastPower(Matrix x,int y)
{
Matrix o;o.build();
while(y>0)
{
if(y&1) o=mul(o,x,0);
y>>=1,x=mul(x,x,0);
}
return o;
}
signed main()
{
Matrix bs,ans;
m=read(),a=read(),c=read(),x0=read(),n=read(),g=read();
ans.a[1][1]=1,ans.a[1][2]=x0,
bs.a[1][1]=1,bs.a[1][2]=c,bs.a[2][2]=a;
bs=FastPower(bs,n),ans=mul(ans,bs,1);
write(ans.a[1][2]%g);
return 0;
}