欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

⭐⭐⭐⭐⭐【快速幂】矩阵幂

程序员文章站 2024-03-17 08:43:52
...

题目描述

⭐⭐⭐⭐⭐【快速幂】矩阵幂

知识点

快速幂的巧用

我的实现

码前思考

  1. 这道题目用的是快速幂相关地思想,而不是简单的快速幂模板

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 20;

int a[maxn][maxn],b[maxn][maxn];
int n,k;

//C++数组传的是引用,需要谨慎修改 
void multi(int a[][maxn],int b[][maxn]){//注意这里的表达!二维数组的表示 
	int tmp[maxn][maxn];
	fill(tmp[0],tmp[0]+maxn*maxn,0);
	
	//然后就是矩阵的乘法
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			for(int k=0;k<n;k++){
				tmp[i][j] += a[i][k]*b[k][j]; 
			}
		}
	}
	
	//然后就是重新赋值
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			a[i][j]=tmp[i][j];
		}
	}	
} 

int main(){

	while(scanf("%d %d",&n,&k)!=EOF){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				scanf("%d",&a[i][j]);
			}
		}
		
		int ans[maxn][maxn];
		fill(ans[0],ans[0]+maxn*maxn,0);
		//初始化为单位矩阵
		for(int i=0;i<n;i++){
			ans[i][i]=1;
		} 
		 
		//读取完之后就是神奇的矩阵幂啦~
		while(k>0){
			if(k&1==1){
				multi(ans,a);	
			}
			multi(a,a);
			k=k>>1;	
		}
		
		//然后就输出
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				printf("%d",ans[i][j]);
				if(j!=n-1){
					printf(" ");
				}else{
					printf("\n");
				}
			}
		} 
	} 
	return 0;
}

码后反思

  1. 快速幂的思想还是要活学活用的,不能仅仅只会数的快速幂~
  2. 初始化时,要将矩阵全部设置为0,不然计算会出错;
  3. 二维数组传入函数时,二维数组的第二维需要显式地表示出来~
  4. C++函数传递的是引用,而不是值,所以可以直接对数组进行修改。
相关标签: # 数学问题

上一篇: HDU 1050

下一篇: 638. Shopping Offers