学斐波那契数矩阵快速幂时,想练手做矩阵快速幂,结果传参不停的错。
在各站找方法,大多数都是用结构体AC的。
于是在请教老师的基础上,终于对了
我的方法是把答案赋予单位矩阵,即f[i][i] = 1,然后矩阵A连乘即可。
终于AC了
中间查错查了一下午,最终发现temp数组,定义的是temp[l][l]={0},
这个局部变量可能不稳定?
改成temp[maxl][maxl]={0}就没有问题了,具体的原因有待再查清楚。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>//矩阵快速幂
using namespace std;
typedef long long LL;
long long m = 1000000007;
const long long maxl=110;
long long l, n;
int temp[maxl][maxl];
int a[maxl][maxl], f[maxl][maxl];
void mul(int c[][maxl], int a[][maxl], int b[][maxl]) {
memset(temp,0,sizeof temp);
for (int i = 0; i < l; i ++ )
for (int j = 0; j < l; j ++ )
for (int k = 0; k < l; k ++ )
temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % m;
memcpy(c, temp, sizeof temp);
}
int main(){
cin >> l >> n;//n就是原题的k次幂
for(int i = 0; i < l; i++){
for(int j = 0; j < l; j++){
cin >> a[i][j];
}
f[i][i] = 1;
}
while (n){
if (n & 1) mul(f, f, a); // res = res * a
mul(a, a, a); // a = a * a
n >>= 1;
}
for(int i = 0; i < l; i++){
for(int j = 0; j < l; j++)
cout << f[i][j] << " ";
cout << endl;
}
return 0;
}
第一次写分享,分享一下陪12岁孩子打竞赛的过程吧,虽然痛苦,但是AC的快乐比工作的快乐多了100倍呀。今年开始陪他学竞赛,曾经用了几个熬夜弄明白装物品是咋回事,从此就走上了在他做题之前,我先把知识点和正确答案都做出来之路,越努力越幸运,噢力给!