結果
| 問題 | No.793 うし数列 2 |
| ユーザー |
 spihill
|
| 提出日時 | 2019-02-23 01:24:56 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 8,923 bytes |
| コンパイル時間 | 2,139 ms |
| コンパイル使用メモリ | 183,548 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-11-26 11:03:19 |
| 合計ジャッジ時間 | 2,863 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;#define int ll#define rep(i, a) for (int i = 0; (i) < (int) (a); (i)++)#define reps(i, a, b) for (int i = (int) (a); (i) < (int) (b); (i)++)#define rrep(i, a) for (int i = (int) a-1; (i) >= 0; (i)--)#define rreps(i, a, b) for (int i = (int) (a)-1; (i) >= (int) (b); (i)--)#define MP(a, b) make_pair((a), (b))#define PB(a) push_back((a))#define all(v) (v).begin(), (v).end()#define PERM(v) next_permutation(all(v))#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())#define CIN(type, x) type x;cin >> x#define TRUE__ "CONTINUE"#define FALSE__ "GAMEOVER"#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}#define YES(f) if((f)){cout << "YES" << endl;}else{cout << "NO" << endl;}#define Yes(f) if((f)){cout << "Yes" << endl;}else{cout << "No" << endl;}#define MINV(v) min_element(all(v))#define MAXV(v) max_element(all(v))#define MIN3(a, b, c) min(min(a, b), c)#define MIN4(a, b, c, d) min(MIN3(a, b, c), d)#define MIN5(a, b, c, d, e) min(MIN4(a, b, c, d), e)#define MIN6(a, b, c, d, e, f) min(MIN5(a, b, c, d, e), f)#define MAX3(a, b, c) max(max(a, b), c)#define MAX4(a, b, c, d) max(MAX3(a, b, c), d)#define MAX5(a, b, c, d, e) max(MAX4(a, b, c, d), e)#define MAX6(a, b, c, d, e, f) max(MAX5(a, b, c, d, e), f)#define RANGE(a, b, c) ((a) <= (b) && (b) < (c))#define RANGE2D(a, b, c, d, e, f) (RANGE((a), (c), (e)) && RANGE((b), (d), (f)))#define chmin(a, b) a = min(a, (b))#define chmin3(a, b, c) a = MIN3(a, (b), (c))#define chmin4(a, b, c, d) a = MIN4(a, (b), (c), (d))#define chmin5(a, b, c, d, e) a = MIN5(a, (b), (c), (d), (e))#define chmin6(a, b, c, d, e, f) a = MIN6(a, (b), (c), (d), (e), (f))#define chmax(a, b) a = max(a, (b))#define chmax3(a, b, c) a = MAX3(a, (b), (c))#define chmax4(a, b, c, d) a = MAX4(a, (b), (c), (d))#define chmax5(a, b, c, d, e) a = MAX5(a, (b), (c), (d), (e))#define chmax6(a, b, c, d, e, f) a = MAX6(a, (b), (c), (d), (e), (f))#define RS resize#define CINV(v, N) do {\v.RS(N);\rep(i, N) cin >> v[i];\} while (0);#define RCINV(v, N) do {\v.RS(N);\rrep(i, N) cin >> v[i];\} while (0);#define fcout cout << fixed << setprecision(12)#define MOD 1000000007template<class T>inline T GET() {T x;cin >> x;return x;}void init();void solve();signed main(){init();solve();}namespace mylib {using namespace std;static const int mod = 1000000007;struct ModInt {int value;ModInt(int x) : value(x) {}ModInt(void) : value(0) {}inline ModInt& operator+=(const ModInt& rhs){(*this) += rhs.value;return *this;}inline ModInt& operator+=(const int rhs){value += rhs;value %= mod;return *this;}inline ModInt& operator-=(const ModInt& rhs){(*this) -= rhs.value;return *this;}inline ModInt& operator-=(const int rhs){value += mod - rhs;value %= mod;return *this;}inline ModInt& operator*=(const ModInt& rhs){(*this) *= rhs.value;return *this;}inline ModInt& operator*=(const int rhs){long long res = (long long) value * rhs;value = res % mod;return *this;}inline ModInt& operator/=(const ModInt& rhs){(*this) /= rhs.value;return *this;}inline ModInt& operator/=(const int rhs){long long res = modpow(rhs);(*this) *= res;return *this;}inline ModInt& operator=(const ModInt& rhs){(*this) = rhs.value;return *this;}inline ModInt& operator=(const int& rhs){(*this).value = rhs % mod;return *this;}inline int operator==(const ModInt& rhs) const{return (*this) == rhs.value;}inline int operator==(const int rhs) const{return (*this).value == rhs % mod;}inline int operator!=(const ModInt& rhs) const{return (*this) != rhs.value;}inline int operator!=(const int rhs) const{return (*this).value != rhs % mod;}int modpow(const int val, int p = mod - 2){if (p == 0) return 1;long long res = 1;if (p % 2) {res = val;}long long t = modpow(val, p / 2);t = t * t % mod;res = res * t % mod;return (int) res;}operator int() const{return value;}};ostream& operator<<(ostream& lhs, const ModInt& rhs){lhs << rhs.value;return lhs;}istream& operator>>(istream& lhs, ModInt& rhs){long long t;lhs >> t;rhs.value = t % mod;return lhs;}const ModInt operator+(const ModInt& lhs, const ModInt& rhs) {return ModInt(lhs) += rhs;}const ModInt operator+(const ModInt& lhs, const int rhs) {return ModInt(lhs) += rhs;}const ModInt operator+(int lhs, const ModInt& rhs) {return ModInt(lhs) += rhs;}const ModInt operator-(const ModInt& lhs, const ModInt& rhs) {return ModInt(lhs) -= rhs;}const ModInt operator-(const ModInt& lhs, const int rhs) {return ModInt(lhs) -= rhs;}const ModInt operator-(int lhs, const ModInt& rhs) {return ModInt(lhs) -= rhs;}const ModInt operator*(const ModInt& lhs, const ModInt& rhs) {return ModInt(lhs) *= rhs;}const ModInt operator*(const ModInt& lhs, const int rhs) {return ModInt(lhs) *= rhs;}const ModInt operator*(int lhs, const ModInt& rhs) {return ModInt(lhs) *= rhs;}const ModInt operator/(const ModInt& lhs, const ModInt& rhs) {return ModInt(lhs) /= rhs;}const ModInt operator/(const ModInt& lhs, const int rhs) {return ModInt(lhs) /= rhs;}const ModInt operator/(int lhs, const ModInt& rhs) {return ModInt(lhs) /= rhs;}const int operator==(int lhs, const ModInt& rhs) {return ModInt(lhs) == rhs;}const int operator!=(int lhs, const ModInt& rhs) {return ModInt(lhs) != rhs;}}using namespace mylib;ModInt mpow(ModInt a, ll b){if (b == 0) return 1;if (b % 2) {return a * mpow(a, b-1);}ModInt r = mpow(a, b/2);return r * r;}namespace mylib{template <typename T>struct Matrix{int row;int column;vector<vector<T>> v;vector<T> &operator[](int i) { return (v[i]); }Matrix(int i, int j){init(i, j);}Matrix(){init(0, 0);}void init(int i, int j){row = i;column = j;v.RS(i, vector<T>(j, 0));}Matrix(const Matrix &cp){row = cp.row;column = cp.column;v = cp.v;}~Matrix(){}Matrix operator=(const Matrix &a){row = a.row;column = a.column;v = a.v;return (*this);}Matrix operator+(const Matrix &a){Matrix r(row, column);for (int i = 0; i < row; i++){for (int j = 0; j < column; j++){r.v[i][j] = v[i][j] + a.v[i][j];}}return (r);}Matrix operator-(const Matrix &a){Matrix r(row, column);for (int i = 0; i < row; i++){for (int j = 0; j < column; j++){r.v[i][j] = v[i][j] - a.v[i][j];}}return (r);}Matrix operator*(const Matrix &a){Matrix r(row, a.column);for (int i = 0; i < row; i++){for (int j = 0; j < a.column; j++){for (int k = 0; k < column; k++){r.v[i][j] += v[i][k] * a.v[k][j];}}}return (r);}Matrix operator*(const int b){Matrix r(row, column);for (int i = 0; i < row; i++){for (int j = 0; j < column; j++){r.v[i][j] = b * v[i][j];}}return (r);}Matrix operator+(const int b){Matrix r(row, column);for (int i = 0; i < row; i++){for (int j = 0; j < column; j++){r.v[i][j] = b + v[i][j];}}return (r);}Matrix operator-(const int b){Matrix r(row, column);for (int i = 0; i < row; i++){for (int j = 0; j < column; j++){r.v[i][j] = v[i][j] - b;}}return (r);}void unit_matrix(){int n = row;for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){v[i][j] = 0;if (i == j)v[i][j] = 1;}}}Matrix<T> accumu_sum(){Matrix<T> r(this->row+1, this->column+1);for (int i = 1; i <= this->row; i++){for (int j = 1; j <= this->column; j++){r[i][j] = this->v[i-1][j-1] + r[i-1][j] + r[i][j-1] - r[i-1][j-1];}}return (r);}T get_sum_accumu(int r1, int c1, int r2, int c2) //半開区間で指定{return v[r2][c2] + v[r1][c1] - v[r2][c1] - v[r1][c2];}Matrix transposed(){Matrix t(column, row);for (int i = 0; i < row; i++){for (int j = 0; j < column; j++){t[j][i] = v[i][j];}}return (t);}};}using namespace mylib;Matrix<ModInt> mpow(Matrix<ModInt> x, ll y){if (y == 1) {return x;}if (y % 2) {return x * mpow(x, y-1);}auto r = mpow(x, y/2);return r * r;}void init(){int N;cin >> N;if (N == 1) {cout << 13 << endl;return;}Matrix<ModInt> A(2, 2);A[0][0] = 10;A[0][1] = 3;A[1][0] = 0;A[1][1] = 1;A = mpow(A, N-1);Matrix<ModInt> B(2, 1);B[0][0] = 13;B[1][0] = 1;Matrix<ModInt> C(2, 1);C = A * B;cout << C[0][0] << endl;}void solve(){}