結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー |
![]() |
提出日時 | 2019-09-21 00:02:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 5,889 bytes |
コンパイル時間 | 1,232 ms |
コンパイル使用メモリ | 101,752 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-15 05:54:26 |
合計ジャッジ時間 | 2,797 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#include <cstdio>#include <cstdlib>#include <algorithm>#include <vector>#include <cstring>#include <queue>#include <set>#include <unordered_set>#include <unordered_map>#include <map>#include <functional>#include <cmath>#include <cassert>#include <string>#include <iostream>using namespace std;typedef long long ll;ll MOD = 1000000007;typedef pair<int, int> P;template <class T>ostream &operator<<(ostream &o, const vector<T> &v){o << "{";for (int i = 0; i < (int)v.size(); i++)o << (i > 0 ? ", " : "") << v[i];o << "}";return o;}template <int mod>struct ModInt{int x;ModInt() : x(0) {}ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}ModInt &operator+=(const ModInt &p){if ((x += p.x) >= mod)x -= mod;return *this;}ModInt &operator-=(const ModInt &p){if ((x += mod - p.x) >= mod)x -= mod;return *this;}ModInt &operator*=(const ModInt &p){x = (int)(1LL * x * p.x % mod);return *this;}ModInt &operator/=(const ModInt &p){*this *= p.inverse();return *this;}ModInt operator-() const { return ModInt(-x); }ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }bool operator==(const ModInt &p) const { return x == p.x; }bool operator!=(const ModInt &p) const { return x != p.x; }ModInt inverse() const{int a = x, b = mod, u = 1, v = 0, t;while (b > 0){t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);}return ModInt(u);}ModInt pow(int64_t n) const{ModInt ret(1), mul(x);while (n > 0){if (n & 1)ret *= mul;mul *= mul;n >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const ModInt &p){return os << p.x;}friend istream &operator>>(istream &is, ModInt &a){int64_t t;is >> t;a = ModInt<mod>(t);return (is);}};const int mod = 1e9 + 7;using modint = ModInt<mod>;template <class T>struct Matrix{vector<vector<T>> A;Matrix() {}Matrix(size_t n, size_t m) : A(n, vector<T>(m, 0)) {}Matrix(size_t n) : A(n, vector<T>(n, 0)){};size_t height() const{return (A.size());}size_t width() const{return (A[0].size());}inline const vector<T> &operator[](int k) const{return (A.at(k));}inline vector<T> &operator[](int k){return (A.at(k));}static Matrix I(size_t n){Matrix mat(n);for (int 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 (int i = 0; i < n; i++)for (int j = 0; j < m; 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 (int i = 0; i < n; i++)for (int j = 0; j < m; 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());vector<vector<T>> C(n, vector<T>(m, 0));for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)for (int k = 0; k < p; k++)C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]);A.swap(C);return (*this);}Matrix &operator^=(long long k){Matrix B = Matrix::I(height());while (k > 0){if (k & 1)B *= *this;*this *= *this;k >>= 1LL;}A.swap(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^(const long long k) const{return (Matrix(*this) ^= k);}friend ostream &operator<<(ostream &os, Matrix &p){size_t n = p.height(), m = p.width();for (int i = 0; i < n; i++){os << "[";for (int j = 0; j < m; j++){os << p[i][j] << (j + 1 == m ? "]\n" : ",");}}return (os);}T determinant(){Matrix B(*this);assert(width() == height());T ret = 1;for (int i = 0; i < width(); i++){int idx = -1;for (int j = i; j < width(); j++){if (B[j][i] != 0)idx = j;}if (idx == -1)return (0);if (i != idx){ret *= -1;swap(B[i], B[idx]);}ret *= B[i][i];T vv = B[i][i];for (int j = 0; j < width(); j++){B[i][j] /= vv;}for (int j = i + 1; j < width(); j++){T a = B[j][i];for (int k = 0; k < width(); k++){B[j][k] -= B[i][k] * a;}}}return (ret);}};int main(){ios::sync_with_stdio(false);cin.tie(0);int a, b, n;cin >> a >> b >> n;Matrix<modint> m(2);m[0][0] = a;m[0][1] = b;m[1][0] = 1;//m[1][1] = 0;m ^= n;cout << m[1][0] << endl;}