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;
}
调对必关