关于矩阵快速幂求斐波那契数列
  • 板块学术版
  • 楼主liyelei
  • 当前回复7
  • 已保存回复7
  • 发布时间2025/7/31 12:47
  • 上次更新2025/7/31 17:00:49
查看原帖
关于矩阵快速幂求斐波那契数列
1385862
liyelei楼主2025/7/31 12:47

rt,求dalao帮我调一下我的代码:

#include <iostream>
#include <cstring>
#define rep(i, a, b) for (int i = a; i <= b; i++)
const int mod = 1e9 + 7;
struct Matrix {
	int m[4][4];
};
Matrix MatrixMul(Matrix a, Matrix b, int la, int lb, int lc) {
	Matrix c;
	memset(c.m, 0, sizeof(c.m));
	rep(i, 1, la) {
		rep(k, 1, lb) {
			if (a.m[i][k]) {
				rep(j, 1, lc) {
					c.m[i][j] += a.m[i][k] * b.m[k][j];
					c.m[i][j] %= mod;
				}
			}
		}
	}
	return c;
}
Matrix MatrixPow(Matrix a, int b, int l) {
	Matrix res;
	for (int i = 1; i <= l; i++) {
		res.m[i][i] = 1;
	}
	while (b) {
		if (b % 2) res = MatrixMul(res, a, l, l, l);
		a = MatrixMul(a, a, l, l, l);
		b >>= 1;
	}	
	return res;
}
int main() {
	int n;
	std::cin >> n;
	Matrix a, b, c;
	a.m[1][1] = a.m[1][2] = 1;
	b.m[1][1] = b.m[1][2] = b.m[2][1] = 1;
	b.m[2][2] = 0;
	b = MatrixPow(b, n - 2, 2);
	c = MatrixMul(a, b, 1, 2, 2);
	std::cout << c.m[1][1];
	return 0;
}

调对必关

2025/7/31 12:47
加载中...