結果
| 問題 | No.891 隣接3項間の漸化式 |
| ユーザー |
 MarcusAureliusAntoninus
|
| 提出日時 | 2019-09-20 22:24:40 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 5,540 bytes |
| コンパイル時間 | 2,016 ms |
| コンパイル使用メモリ | 204,404 KB |
| 最終ジャッジ日時 | 2025-01-07 18:45:33 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 39 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:244:19: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=]
244 | scanf("%lld%lld%lld", &a, &b, &n);
| ~~~^ ~~
| | |
| | int64_t* {aka long int*}
| long long int*
| %ld
main.cpp:244:23: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 3 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=]
244 | scanf("%lld%lld%lld", &a, &b, &n);
| ~~~^ ~~
| | |
| | int64_t* {aka long int*}
| long long int*
| %ld
main.cpp:244:27: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 4 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=]
244 | scanf("%lld%lld%lld", &a, &b, &n);
| ~~~^ ~~
| | |
| | int64_t* {aka long int*}
| long long int*
| %ld
main.cpp:244:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
244 | scanf("%lld%lld%lld", &a, &b, &n);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#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;}