結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー | MarcusAureliusAntoninus |
提出日時 | 2019-09-20 22:24:40 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 5,540 bytes |
コンパイル時間 | 2,283 ms |
コンパイル使用メモリ | 211,492 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 18:14:57 |
合計ジャッジ時間 | 3,508 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 2 ms
5,376 KB |
testcase_30 | AC | 2 ms
5,376 KB |
testcase_31 | AC | 2 ms
5,376 KB |
testcase_32 | AC | 2 ms
5,376 KB |
testcase_33 | AC | 2 ms
5,376 KB |
testcase_34 | AC | 2 ms
5,376 KB |
testcase_35 | AC | 2 ms
5,376 KB |
testcase_36 | AC | 2 ms
5,376 KB |
testcase_37 | AC | 2 ms
5,376 KB |
testcase_38 | AC | 2 ms
5,376 KB |
testcase_39 | AC | 2 ms
5,376 KB |
testcase_40 | AC | 2 ms
5,376 KB |
testcase_41 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> //////////// // ModInt // //////////// // 四則演算の最も左に存在する値がModIntでなければキャストでバグる // 例えばx = mint * 1000;やx = ModInt(1000) * mint;はいいがx = 1000 * mint;は駄目。 template<int64_t mod_ = 1'000'000'007> class ModInt { private: int64_t integer_; public: constexpr ModInt(const int64_t initial_number = 0) : integer_(initial_number){} // 四則演算 constexpr ModInt operator+(const ModInt& operand) const { ModInt ret{this->integer_ + operand.integer_}; if (ret.integer_ >= mod_) ret.integer_ -= mod_; return ret; } constexpr ModInt operator-(const ModInt& operand) const { ModInt ret{this->integer_ - operand.integer_}; if (ret.integer_ < 0) ret.integer_ += mod_; return ret; } constexpr ModInt operator*(const ModInt& operand) const { return {this->integer_ * operand.integer_ % mod_}; } constexpr ModInt operator/(const ModInt& operand) const { return *this * (operand ^ (mod_ - 2)); } // 単項演算子 constexpr ModInt& operator++() { if (integer_ + 1 == mod_) integer_ = 0; else integer_++; return *this; } constexpr ModInt& operator--() { if (integer_ == 0) integer_ = mod_ - 1; else integer_--; return *this; } constexpr ModInt operator+() { return *this; } constexpr ModInt operator-() { if (integer_ == 0) return ModInt(0ll); else return ModInt(mod_ - integer_); } // 累乗 constexpr ModInt operator^(const int64_t operand) const { ModInt ret{1}, pow_ope{this->integer_}; for (int64_t pow{operand}; pow > 0; pow >>= 1) { if (pow & 1) ret *= pow_ope; pow_ope *= pow_ope; } return ret; } // 代入 constexpr ModInt& operator=(const ModInt& operand) { this->integer_ = operand.integer_; return *this; } constexpr ModInt& operator+=(const ModInt& operand) { *this = *this + operand; return *this; } constexpr ModInt& operator-=(const ModInt& operand) { *this = *this - operand; return *this; } constexpr ModInt& operator*=(const ModInt& operand) { *this = *this * operand; return *this; } constexpr ModInt& operator/=(const ModInt& operand) { *this = *this / operand; return *this; } // その他 constexpr operator int64_t() { return integer_; } constexpr ModInt getOne() const { return ModInt(1ll); } constexpr ModInt getZero() const { return ModInt(0ll); } }; using Mint = ModInt<>; //////////// // 行列型 // /////////// // 加算、減算、乗算をもつM×N型行列 // M=Nで環をつくる template<typename T = int64_t> class Matrix { private: using RowVector = std::vector<T>; std::vector<RowVector> container_; // 必要に応じて書換 const T ring_one{1ll}; const T ring_zero{}; public: const int M, N; Matrix(const int row_size, const int column_size) : M(row_size), N(column_size), container_(row_size, RowVector(column_size)){} // ムーブコンストラクタ Matrix(Matrix&& mat) : M(mat.M), N(mat.N), container_(std::move(mat.container_)){} // コピーコンストラクタ Matrix(const Matrix& mat) : M(mat.M), N(mat.N), container_(mat.container_){} // 要素アクセス RowVector& operator[](const int r) { return container_[r]; } const RowVector& operator[](const int r) const { return container_[r]; } // イテレータ typename decltype(container_)::iterator begin(){ return container_.begin(); } typename decltype(container_)::iterator end(){ return container_.end(); } // 環の演算 Matrix operator+(const Matrix& mat) const { Matrix ret{*this}; for (int r_i{}; r_i < M; r_i++) for (int c_i{}; c_i < N; c_i++) ret[r_i][c_i] += mat[r_i][c_i]; return std::move(ret); } Matrix operator-(const Matrix& mat) const { Matrix ret{*this}; for (int r_i{}; r_i < M; r_i++) for (int c_i{}; c_i < N; c_i++) ret[r_i][c_i] -= mat[r_i][c_i]; return std::move(ret); } Matrix operator*(const Matrix& mat) const { Matrix ret(this->M, mat.N); for (int r_i{}; r_i < this->M; r_i++) for (int c_i{}; c_i < mat.N; c_i++) for (int l_i{}; l_i < this->N; l_i++) ret[r_i][c_i] += (*this)[r_i][l_i] * mat[l_i][c_i]; return std::move(ret); } std::vector<T> operator*(const std::vector<T>& vec) const { std::vector<T> ret(M); for (int r_i{}; r_i < M; r_i++) for (int c_i{}; c_i < N; c_i++) ret[r_i] += (*this)[r_i][c_i] * vec[c_i]; return std::move(ret); } // 累乗 Matrix operator^(const int64_t index) const { Matrix ret((*this).getOne()), pow(*this); for (int64_t i{index}; i > 0; i >>= 1) { if (i & 1) ret *= pow; pow *= pow; } return std::move(ret); } // 代入演算子 Matrix& operator=(const Matrix& mat) { this->container_ = mat.container_; return *this; } Matrix& operator+=(const Matrix& mat) { *this = *this + mat; return *this; } Matrix& operator-=(const Matrix& mat) { *this = *this - mat; return *this; } Matrix& operator*=(const Matrix& mat) { *this = *this * mat; return *this; } // ゼロ行列と単位行列 constexpr Matrix getOne() const { Matrix ret(M, N); for (int i{}; i < N; i++) ret[i][i] = ring_one; return std::move(ret); } constexpr Matrix getZero() const { return Matrix(M, N); } }; int main() { int64_t a, b, n; scanf("%lld%lld%lld", &a, &b, &n); using Mat = Matrix<Mint>; Mat mat(2, 2); mat[0][0] = Mint(0ll); mat[0][1] = Mint(1ll); mat[1][0] = Mint(b); mat[1][1] = Mint(a); std::vector<Mint> vec{0, 1}; std::cout << ((mat ^ n) * vec)[0] << std::endl; return 0; }