結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー |
![]() |
提出日時 | 2020-10-17 15:18:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 5,088 bytes |
コンパイル時間 | 2,476 ms |
コンパイル使用メモリ | 201,236 KB |
最終ジャッジ日時 | 2025-01-15 10:54:33 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
// Template #define FORESTED #include "bits/stdc++.h" #define rep_override(x, y, z, name, ...) name #define rep2(i, n) for (int i = 0; i < (int)(n); ++i) #define rep3(i, l, r) for (int i = (int)(l); i < (int)(r); ++i) #define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__) #define per(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i) #define all(x) (x).begin(), (x).end() using namespace std; using ll = long long; constexpr int inf = 1001001001; constexpr ll INF = 3003003003003003003LL; template <typename T> inline bool chmin(T &x, const T &y) { if (x > y) { x = y; return true; } return false; } template <typename T> inline bool chmax(T &x, const T &y) { if (x < y) { x = y; return true; } return false; } struct IOSET { IOSET() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); } } ioset; template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (T &element : vec) is >> element; return is; } template <typename T> vector<T> operator--(vector<T> &vec) { for (T &element : vec) --element; return vec; } // Matrix template <typename T> class Matrix { int h, w; std::vector<std::vector<T>> vec; public: Matrix(int h_, int w_) : h(h_), w(w_), vec(h_, std::vector<T>(w_, T(0))) {} const std::vector<T> &operator[](int x) const { return vec.at(x); } std::vector<T> &operator[](int x) { return vec.at(x); } Matrix &operator+=(const Matrix<T> &x) { assert(h == x.h && w == x.w); for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { vec[i][j] += x.vec[i][j]; } } return *this; } Matrix &operator-=(const Matrix<T> &x) { assert(h == x.h && w == x.w); for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { vec[i][j] -= x.vec[i][j]; } } return *this; } Matrix &operator*=(const Matrix<T> &x) { assert(w == x.h); std::vector<std::vector<T>> res(h, std::vector<T>(x.w, T(0))); for (int i = 0; i < h; ++i) { for (int j = 0; j < x.w; ++j) { for (int k = 0; k < w; ++k) { res[i][j] += vec[i][k] * x.vec[k][j]; } } } vec.swap(res); return *this; } Matrix operator+(const Matrix<T> &x) const { return Matrix(*this) += x; } Matrix operator-(const Matrix<T> &x) const { return Matrix(*this) -= x; } Matrix operator*(const Matrix<T> &x) const { return Matrix(*this) *= x; } Matrix pow(long long x) const { assert(x >= 0 && h == w); Matrix<T> a(h, h), b(*this); for (int i = 0; i < h; ++i) a[i][i] = T(1); while (x) { if (x & 1) { a *= b; } b *= b; x >>= 1; } return a; } }; // Mod-Int template <int MOD> struct ModInt { static_assert(MOD >= 1); long long val; ModInt() = default; ModInt(long long x) : val(x % MOD + (x < 0 ? MOD : 0)) {} ModInt<MOD> &operator+= (const ModInt<MOD> &x) { if ((val += x.val) >= MOD) val -= MOD; return *this; } ModInt<MOD> &operator-= (const ModInt<MOD> &x) { if ((val -= x.val) < 0) val += MOD; return *this; } ModInt<MOD> &operator*= (const ModInt<MOD> &x) { (val *= x.val) %= MOD; return *this; } ModInt<MOD> operator+ (const ModInt<MOD> &x) const { return ModInt(*this) += x; } ModInt<MOD> operator- (const ModInt<MOD> &x) const { return ModInt(*this) -= x; } ModInt<MOD> operator* (const ModInt<MOD> &x) const { return ModInt(*this) *= x; } ModInt<MOD> pow(long long t) const { assert(t >= 0); ModInt<MOD> res(1), now(*this); while (t) { if (t & 1) res *= now; now *= now; t >>= 1; } return res; } ModInt<MOD> inv() const { return pow(MOD - 2); } ModInt<MOD> &operator/= (const ModInt<MOD> &x) { return *this *= x.pow(MOD - 2); } ModInt<MOD> operator/ (const ModInt<MOD> &x) const { return ModInt(*this) /= x; } friend std::istream &operator>> (std::istream &is, ModInt<MOD> &x) { long long a; is >> a; x = ModInt<MOD>(a); return is; } friend std::ostream &operator<< (std::ostream &os, const ModInt<MOD> &x) { os << x.val; return os; } }; constexpr int mod = 1000000007; using mint = ModInt<mod>; // Main int main() { int a, b, n; cin >> a >> b >> n; Matrix<mint> mat(2, 2); mat[0][0] = mint(a); mat[0][1] = mint(b); mat[1][0] = mint(1); Matrix<mint> ans = mat.pow(n); cout << ans[1][0] << "\n"; }