第二个样例过不去
查看原帖
第二个样例过不去
726139
残阳如血楼主2024/5/10 19:29
[0111]×[fi−2fi−1]=[fi−1fi=fi−1+fi−2]\begin{bmatrix} 0&1\\ 1&1 \end{bmatrix} \times \begin{bmatrix} f_{i-2}\\ f_{i-1} \end{bmatrix} = \begin{bmatrix} f_{i-1}\\ f_{i}=f_{i-1}+f_{i-2} \end{bmatrix}

那么为什么这样写对于输入 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;
}
2024/5/10 19:29
加载中...