首页 > 其他分享 >矩阵快速幂

矩阵快速幂

时间:2022-11-17 21:01:45浏览次数:91  
标签:Matrix int 矩阵 base il mul 快速 define

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

标签:Matrix,int,矩阵,base,il,mul,快速,define
From: https://www.cnblogs.com/Bertidurlah/p/16900920.html

相关文章

  • 自学Java注意,注意细节快速掌握
    自学Java必须注意的问题    第一,刚开始学Java编程的时候,确实挺嘈人的,一个非常小的问题,可能就是一个字母拼错了,你就是找不出问题在哪里,这是每个初学者都会面临的问......
  • Valine——一款快速、简洁且高效的无后端评论系统
    简介Valine-是一款基于LeanCloud的快速、简洁且高效的无后端评论系统。他快速、简洁且高效,使用起来非常简单。开始请先登录或注册LeanCloud,进入控制台后点击左下角......
  • 【模板】快速沃尔什变换 FWT
    解决形如\[c_k=\sum_{i\oplusj=k}a_ib_j.\]的卷积式子,这里解决\(\oplus=\{\cup,\cap,\text{xor}\}\)。#include<cstdio>#include<cstring>#include<algorithm>u......
  • Nginx快速入门
    参考文章:https://www.kuangstudy.com/bbs/1353634800149213186公司产品出现瓶颈?我们公司项目刚刚上线的时候,并发量小,用户使用的少,所以在低并发的情况下,一个jar包启动应用......
  • 矩阵分解和信息论基础
    学习总结文章目录​​学习总结​​​​一、矩阵分解​​​​二、信息论​​​​熵(Entropy)​​​​联合熵​​​​条件熵​​​​互信息​​​​相对熵​​​​交叉熵​​......
  • 快速创建软件安装包-ClickOnce
    大家好,我是沙漠尽头的狼。.NET是免费,跨平台,开源,用于构建所有应用的开发人员平台。今天介绍使用ClickOnce制作软件安装包,首先我们先了解什么是ClickOne。1.什么是ClickOnce......
  • Bootstrap概述、快速入门
    Bootstrap概述概念:一个前端开发的框架,Bootstrap,来自Twitter,是目前很受欢迎的前端框架。Bootstrap是基于HTML,CSS,JavaScript的,它简洁灵活,使得Web开发更加快捷框架:一个......
  • AIPHD科技文教产品矩阵体验设计
    AIPHD科技文教专注于科技文教,由AIPHD公众号,AIPHD英语、AI智能古诗、AIPHD科技心理等具有独立功能的APP产品矩阵组成,同时将AIMANT星球作为情感辅助。AIPHD系列更注重于大学......
  • VBA代码助手 VBA中右键快速收藏代码功能 VBA随时收藏代码
    VBA代码助手下载地址VBA代码收藏功能简介本功能要求VBA代码助手最低版本V3.8.6.0 之前神键手代码提示必须打开关键词表或者在代码管理窗口才能添加和编辑VBA代码库,为了......
  • 详解主成分分析PCA与奇异值分解SVD-降维后的矩阵components_ & inverse_transform【菜
    视频作者:[菜菜TsaiTsai]链接:[【技术干货】菜菜的机器学习sklearn【全85集】Python进阶_哔哩哔哩_bilibili]V(k,n)这个矩阵保存在.components_这个属性当中我们之前谈到......