⭐⭐⭐⭐⭐【快速幂】矩阵幂
程序员文章站
2024-03-17 08:43:52
...
题目描述
知识点
快速幂的巧用
我的实现
码前思考
- 这道题目用的是快速幂相关地思想,而不是简单的快速幂模板
代码实现
#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;
}
码后反思
- 快速幂的思想还是要活学活用的,不能仅仅只会数的快速幂~
- 初始化时,要将矩阵全部设置为0,不然计算会出错;
- 二维数组传入函数时,二维数组的第二维需要显式地表示出来~
- C++函数传递的是引用,而不是值,所以可以直接对数组进行修改。
上一篇: HDU 1050
下一篇: 638. Shopping Offers