結果
問題 | No.718 行列のできるフィボナッチ数列道場 (1) |
ユーザー |
![]() |
提出日時 | 2021-03-09 15:27:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 2,869 bytes |
コンパイル時間 | 2,013 ms |
コンパイル使用メモリ | 204,804 KB |
最終ジャッジ日時 | 2025-01-19 13:04:52 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> template<typename T> class matrix { public: matrix() {} matrix(size_t n, size_t m) : A(n, std::vector<T>(m)) {} matrix(size_t n) : A(n, std::vector<T>(n)) {} size_t height() const { return A.size(); } size_t width() const { return A[0].size(); } inline const std::vector<T>& operator[](size_t k) const { return A[k]; } inline std::vector<T>& operator[](size_t k) { return A[k]; } static matrix I(size_t n) { matrix mat(n); for (size_t i = 0; i < n; ++i) mat[i][i] = 1; return mat; } matrix& operator+=(const matrix& B) { size_t n = height(), m = width(); assert(n == B.height() && m == B.width()); for (size_t i = 0; i < n; ++i) for (size_t j = 0; j < n; ++j) (*this)[i][j] += B[i][j]; return *this; } matrix& operator-=(const matrix& B) { size_t n = height(), m = width(); assert(n == B.height() && m == B.width()); for (size_t i = 0; i < n; ++i) for (size_t j = 0; j < n; ++j) (*this)[i][j] -= B[i][j]; return *this; } matrix& operator*=(const matrix& B) { size_t n = height(), m = B.width(), p = width(); assert(p == B.height()); std::vector C(n, std::vector<T>(m)); for (size_t i = 0; i < n; ++i) for (size_t j = 0; j < m; ++j) for (size_t k = 0; k < p; ++k) C[i][j] += (*this)[i][k] * B[k][j]; A = std::move(C); return *this; } matrix& operator^=(unsigned long long k) { matrix B = matrix::I(height()); while (k > 0) { if (k & 1) B *= *this; *this *= *this; k >>= 1; } A = std::move(B.A); return *this; } matrix operator+(const matrix& B) const { return matrix(*this) += B; } matrix operator-(const matrix& B) const { return matrix(*this) -= B; } matrix operator*(const matrix& B) const { return matrix(*this) *= B; } matrix operator^(unsigned long long k) const { return matrix(*this) ^= k; } friend std::ostream& operator<<(std::ostream& os, matrix& p) { size_t n = p.height(), m = p.width(); for (size_t i = 0; i < n; ++i) { os << '['; for (size_t j = 0; j < m; ++j) { os << p[i][j] << (j + 1 == m ? "]\n" : ","); } } return os; } private: std::vector<std::vector<T>> A; }; #include <atcoder/modint> using namespace atcoder; using mint = modint1000000007; int main() { size_t n; std::cin >> n; matrix<mint> A(2); A[0] = {1, 1}; A[1] = {1, 0}; A ^= n; matrix<mint> x(2, 1); x[0] = {1}; x[1] = {0}; auto b = A * x; mint ans = b[0][0] * b[1][0]; std::cout << ans.val() << '\n'; }