Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【题解】矩阵快速幂(分治+代数)

【题解】矩阵快速幂(分治+代数)

作者头像
fishhh
发布于 2022-08-30 11:43:57
发布于 2022-08-30 11:43:57
33400
代码可运行
举报
文章被收录于专栏:OI算法学习笔记OI算法学习笔记
运行总次数:0
代码可运行

题目背景

矩阵快速幂

题目描述

给定 n×n 的矩阵 A,求

输入格式

第一行两个整数 n,k 接下来 n 行,每行 n 个整数,第 i 行的第 j 的数表示

输出格式

输出

共 n 行,每行 n 个数,第 i 行第 j 个数表示

,每个元素对

取模。

输入输出样例

输入 #1

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
2 1
1 1
1 1

输出 #1

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
1 1
1 1

说明/提示

【数据范围】 对于 100% 的数据:

题目分析

先来了解一些矩阵相关的知识

矩阵

矩阵(matrix)。n×m 的矩阵指的是n行,m列的矩阵。

就是指的 2×3的矩阵。

单位矩阵

单位矩阵指的是 对角线上为1,其他位置为0的矩阵。

常用 I 来表示单位矩阵。

矩阵的幂次方

性质

  1. 矩阵乘法满足分配率,结合律,不一定满足交换律
  2. 加法满足交换律和结合律

矩阵满足结合律,所以在求矩阵的幂的时候,可以使用 矩阵快速幂加速。

矩阵快速幂

分治的思路解决矩阵快速幂

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
node matrixPow(node a,ll k){//矩阵的幂次方
	if(k==0){// 0次方
		return I;//矩阵的0次方是单位矩阵
	}
	node t=matrixPow(a,k/2);//求 a^{n/2} 次方
	if(k&1){//判断k是否是奇数
		return matrixMins(matrixMins(t,t),a);
	}else{//k是偶数
		return matrixMins(t,t);
	}
}

代码实现

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=105;
const int M=1e9+7;
struct node{
	ll a[N][N]={0};
	int row,col;
};
node I;//单位矩阵

node matrixMins(node a,node b){//矩阵乘法
	node c;//答案矩阵
	c.row=a.row;
	c.col=b.col;
	int n=c.row,p=c.col,m=a.col;
	//计算矩阵乘法
	for(int i=1;i<=n;i++){
		for(int j=1;j<=p;j++){
			for(int k=1;k<=m;k++){
				c.a[i][j]+=a.a[i][k]*b.a[k][j]%M;
				c.a[i][j]%=M;
			}
		}
	}
	return c;
}
node matrixPow(node a,ll k){//矩阵的幂次方
	if(k==0){// 0次方
		return I;//矩阵的0次方是单位矩阵
	}
	node t=matrixPow(a,k/2);//求 a^{n/2} 次方
	if(k&1){//判断k是否是奇数
		return matrixMins(matrixMins(t,t),a);
	}else{//k是偶数
		return matrixMins(t,t);
	}
}
int main(){
	int n;
	node a;
	ll k;
	cin>>n>>k;
	a.col=a.row=n;
	I.col=I.row=n;
	for(int i=1;i<=n;i++){//输入矩阵A
		for(int j=1;j<=n;j++){
			cin>>a.a[i][j];
			//处理单元矩阵
			if(i==j) I.a[i][j]=1;
			else	I.a[i][j]=0;
		}
	}
	node ans=matrixPow(a,k);//计算a^k
	//输出结果矩阵
	for(int i=1;i<=ans.row;i++){
		for(int j=1;j<=ans.col;j++){
			cout<<ans.a[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

Q.E.D.

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
【HDU 1757】 A Simple Math Problem
Lele now is thinking about a simple function f(x).  If x < 10 f(x) = x.  If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);  And ai(0<=i<=9) can only be 0 or 1 .  Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.
饶文津
2020/05/31
4150
快速幂和矩阵快速幂(待进一步补充)
它可以快速求出斐波那契数列,这里以一个题为例,Fibonacci POJ - 3070
_DIY
2019/08/23
4190
POJ 3233 Matrix Power Series(矩阵快速幂)
Matrix Power Series Time Limit: 3000MS Memory Limit: 131072K Total Submissions: 19338 Accepted: 8161 Description Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak. Input The input contains exactly one
ShenduCC
2018/04/26
6780
POJ 3233 Matrix Power Series(矩阵快速幂)
【题解】斐波那契数列(矩阵快速幂)
题目描述 大家都知道,斐波那契数列是满足如下性质的一个数列: 图片 请你求出 图片 的值。 输入格式 一行一个正整数 n 输出格式 输出一行一个整数表示答案。 输入输出样例 输入 #1 5 输出 #1 5 输入 #2 10 输出 #2 55 说明/提示 【数据范围】 图片 题目分析 题意很简单求斐波那契数列的第nnn项,但是坑点在于n的范围特别大,最大能达到 图片 ,O(n)级别的递归会导致超时。 斐波那契数列的递归公式: 图片 。我们以矩阵的角度来看待这个递推式。 图片 可发现每次矩阵乘
fishhh
2022/08/30
2700
【题解】斐波那契数列(矩阵快速幂)
洛谷P1397 [NOI2013]矩阵游戏(十进制矩阵快速幂)
感觉做这题只要对矩阵乘法理解的稍微一点就能做出来 对于每一行构造一个矩阵 A = a 1       0 b 列与列之间的矩阵为 B = c 1       0 d 最终答案为 $A^{n - 1}B A^{n - 1}B \dots $ 把$A^{n-1}B$看成一项进行快速幂即可
attack
2018/09/30
5440
xmuC语言程序实践week 1 大作业
  给定一个矩阵A,一个非负整数b和一个正整数m,求A的b次方除m的余数。   其中一个nxn的矩阵除m的余数得到的仍是一个nxn的矩阵,这个矩阵的每一个元素是原矩阵对应位置上的数除m的余数。   要计算这个问题,可以将A连乘b次,每次都对m求余,但这种方法特别慢,当b较大时无法使用。下面给出一种较快的算法(用A^b表示A的b次方):   若b=0,则A^b%m=I%m。其中I表示单位矩阵。   若b为偶数,则A^b%m=(A^(b/2)%m)^2%m,即先把A乘b/2次方对m求余,然后再平方后对m求余。   若b为奇数,则A^b%m=(A^(b-1)%m)*a%m,即先求A乘b-1次方对m求余,然后再乘A后对m求余。   这种方法速度较快,请使用这种方法计算A^b%m,其中A是一个2x2的矩阵,m不大于10000。
glm233
2020/09/28
3610
xmuC语言程序实践week 1 大作业
【题解】矩阵加速
题目描述 图片 输入格式 第一行一个整数 T,表示询问个数。 以下 T 行,每行一个正整数 n。 输出格式 每行输出一个非负整数表示答案。 输入输出样例 输入 #1 3 6 8 10 输出 #1 4 9 19 说明/提示 图片 题目分析 图片 代码实现 #include <iostream> #include <cstdio> using namespace std; typedef long long ll; const int N=5; const int M=1e9+7; struct
fishhh
2022/12/02
2310
矩阵快速幂
快速幂算法是用来快速计算指数表达式的值的,例如 210000000,普通的计算方法 2*2*2*2…10000000次,如果一个数字的计算都要计算那么多次的话,那么这个程序一定是失败的。
IsLand1314
2024/10/15
1060
矩阵快速幂
【HDU 2604】Queuing
  f和m两种字母组成字符串,fmf 和 fff 这种为不安全的字符串,现在有2*L个字母,问你有多少安全的字符串。答案mod M。
饶文津
2020/06/02
3080
【矩阵快速幂】简单题学「矩阵快速幂」
这是 LeetCode 上的「1137. 第 N 个泰波那契数」,难度为「简单」。
宫水三叶的刷题日记
2021/09/10
1.1K0
HDU 2157 How many ways??(简单线性DP | | 矩阵快速幂)
题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=2157 这道题目很多人的题解都是矩阵快速幂写的,矩阵快速幂倒是麻烦了许多了。先给DP的方法 dp
ShenduCC
2018/04/26
4780
Java矩阵快速幂实现
之前做题目喷到一题,自己通过递归求解也能做出来,但是数据量一大超过10000,就基本上凉凉了,所以自己之后一直看了别人的解法,认识到了矩阵快速幂的好处,自己之前也碰到过,但是只是简单了解了一下,所以什么东西最好还是精一点的好,略懂是不行的。 首先一般的幂运算,普通的解法就是一次乘,比如说X^12,可能就是简单的12个X相乘,总共计算的c次数就是12次,但是我们可以把12分解成12=4+8,那么只需要计算4次方以及8次方,这样我们一次计算2次方,4次方,8次方,最后直接将4次方与8次方相乘即可,那这样我们最后只计算了4次,次数大大的减少了,所以非常实用。 同理我们也可以将这种运算方式运用到矩阵上。 下面就是详细的代码:
萌萌哒的瓤瓤
2020/08/26
9710
矩阵快速幂小结
由$n \times m$个数$a_{ij}$排成的$n$行$m$列的数表称为$n$行$m$列的矩阵,简称$n \times m$矩阵。
attack
2018/09/17
4570
矩阵快速幂小结
Archived | 307-09-矩阵
定义矩阵A,B,其中A的大小为a \times b,B的大小为b \times c,对于矩阵C=AB中的每一个元素C(i.j),~i\in [1, a],~j\in [1,c],存在以下:
gyro永不抽风
2021/05/21
6160
矩阵快速幂小结
      矩阵快速幂大概是用来解决这样一类问题,当你知道了一个递推式比如a[n]=a[n-1]+a[n-2] 题目要求你求出a[n]。如果n大于1亿怎么办? 不可能用for。解决办法就是根据递推式构
ShenduCC
2018/04/26
7520
矩阵快速幂小结
【矩阵快速幂】简单题学「矩阵快速幂」Ⅱ
这是 LeetCode 上的「剑指 Offer 10- I. 斐波那契数列」,难度为「简单」。
宫水三叶的刷题日记
2021/09/10
6730
矩阵快速幂
tql,ORZ,catch me off ground。 矩阵快速幂 1. 分解来看,是由矩阵乘法,和快速幂组成 矩阵乘法 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) c[i][j]+=a[i][k]*b[k][j]; 快速幂 ll pow_ksm(ll a,ll n) { ll res = 1; while(n) { if(n&1) res = res*a%mod;
AngelNH
2020/04/16
3390
HDU 5667 Sequence(矩阵快速幂)
Problem Description Holion August will eat every thing he has found. Now there are many foods,but he does not want to eat all of them at once,so he find a sequence. fn=⎧⎩⎨⎪⎪1,ab,abfcn−1fn−2,n=1n=2otherwise He gives you 5 numbers n,a,b,c,p,and he will
ShenduCC
2018/04/26
5440
HDU 5667 Sequence(矩阵快速幂)
数学--数论--HDU - 6395 Let us define a sequence as below 分段矩阵快速幂
Your job is simple, for each task, you should output Fn module 109+7. Input The first line has only one integer T, indicates the number of tasks.
风骨散人Chiam
2020/11/06
4240
数论-快速幂、矩阵快速幂
文章目录 快速幂 矩阵快速幂 例题 HDU-2817 HDU-3117 快速幂 ---- image.png int fastpow(int a, int n) { int res = 1; while (n) { if (n & 1) //末位为1 res = (res * a) % mod; a = (a * a) % mod; n >>= 1; //n右移一位 } return res;
唔仄lo咚锵
2020/09/15
5530
相关推荐
【HDU 1757】 A Simple Math Problem
更多 >
领券
💥开发者 MCP广场重磅上线!
精选全网热门MCP server,让你的AI更好用 🚀
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验