前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数学--矩阵快速幂详解

数学--矩阵快速幂详解

作者头像
风骨散人Chiam
发布2020-11-06 00:33:55
3250
发布2020-11-06 00:33:55
举报
文章被收录于专栏:CSDN旧文

引引导:

我们之前都学快速幂:

矩阵也是可以相乘,方阵可以自乘,即乘幂运算。

作用:

将线性递推,优化l o g 2 n log_{2}nlog2​n

模板:

定义矩阵的阶

代码语言:javascript
复制
const int len = 15;

定义转移矩阵

代码语言:javascript
复制
struct node
{
	int mat[len][len]; 
} x, y;

矩阵乘法

代码语言:javascript
复制
node mul(node x, node y)
{
	node tmp;
	for (int i = 0; i < len; i++)
	{
		for (int j = 0; j < len; j++)
		{
			tmp.mat[i][j] = 0;
			for (int k = 0; k < len; k++)
			{
				tmp.mat[i][j] += (x.mat[i][k] * y.mat[k][j]) % mod;
			}
			tmp.mat[i][j] = tmp.mat[i][j] % mod;
		}
	}
	return tmp;
}

矩阵快速幂

代码语言:javascript
复制
node matpow(node x,node y,int num){
	while(num){
		if(num&1){
			y=mul(y,x);
		}
		x=mul(x,x);
		num=num>>1;
	}
	return y;
} 

算法的难点是怎样写出转移矩阵: 一般的递推式

在这里插入图片描述
在这里插入图片描述

关于其他矩阵构造:

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/02/14 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档