那么为什么这样写对于输入 10,输出 10 而非 55?
#include <vector>
#include <iostream>
const int MOD = 1e9 + 7;
typedef long long lint;
template<typename T> // T 表示矩阵存的值的类型
struct Matrix {
int n, m; // n 为行数,m 为列数
std::vector<std::vector<T>> a;
Matrix(int _n = 0, int _m = 0) : n(_n), m(_m) {
a.resize(_n);
for (int i = 0; i < _n; ++i)
a[i].resize(_m);
}
Matrix(const std::vector<std::vector<T>> &_a) : n(_a.size()), m(_a[0].size()), a(_a) {}
Matrix operator*(const Matrix<T> &A) {
if (m != A.n) throw "Error";
Matrix res(n, A.m);
for (int i = 0; i < n; ++i) // 枚举最终矩阵的行
for (int j = 0; j < A.m; ++j) // 枚举最终矩阵的列
for (int k = 0; k < m; ++k) // 枚举 A 的列(B 的行)
res.a[i][j] += a[i][k] * A.a[k][j] % MOD;
return res;
}
Matrix &operator*=(const Matrix<T> &A) {
*this = *this * A;
return *this;
}
};
template <typename T>
std::istream &operator>>(std::istream &is, Matrix<T> &A) { // 读入矩阵
for (int i = 0; i < A.n; ++i)
for (int j = 0; j < A.m; ++j)
is >> A.a[i][j];
return is;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const Matrix<T> &A) { // 输出矩阵
for (int i = 0; i < A.n; ++i) {
for (int j = 0; j < A.m; ++j)
os << A.a[i][j] << ' ';
os << '\n';
}
return os;
}
Matrix<int> qpow(Matrix<int> &P, int b) {
Matrix<int> ans(P);
for (; b; b >>= 1) {
if (b & 1) ans *= P;
P *= P;
}
return ans;
}
int main() {
lint n;
std::cin >> n;
if (n <= 2) return std::cout << "1\n", 0;
Matrix<int> A(std::vector<std::vector<int>>({{1}, {1}}));
Matrix<int> P(std::vector<std::vector<int>>({{0, 1}, {1, 1}}));
std::cout << (qpow(P, n - 2) * A).a[1][0] << std::endl;
return 0;
}