結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー |
|
提出日時 | 2019-09-22 00:32:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,170 bytes |
コンパイル時間 | 1,923 ms |
コンパイル使用メモリ | 174,544 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-19 03:11:18 |
合計ジャッジ時間 | 3,096 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#include <bits/stdc++.h> using namespace std; using T = long long; using vvt = vector<vector<T>>; constexpr long long MOD = 1e9+7; vvt identity_mat(int n){ vvt I(n, vector<T>(n, 0)); for (int i = 0; i != n; ++i) I[i][i] = 1; return I; } vvt matmul(const vvt & a, const vvt & b, const long long mod = MOD){ int n_row = a.size(); int n_col = b[0].size(); assert(a[0].size() == b.size()); vvt c(n_row, vector<T>(n_col, 0)); for (int i = 0; i != n_row; ++i){ for (int j = 0; j != n_col; ++j){ for (int k = 0; k != b.size(); ++k){ c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod; } } } return c; } vvt matpow(vvt mat, long long n, const long long mod = MOD){ // a^n を求める。 assert(mat.size() == mat[0].size()); vvt ans = identity_mat(mat.size()); while (n){ if (n & 1) ans = matmul(ans, mat, mod); mat = matmul(mat, mat, mod); n >>= 1; } return ans; } int main(){ long long a, b, n; cin >> a >> b >> n; vvt mat = {{a, b}, {1LL, 0LL}}; auto p = matpow(mat, n); cout << p[1][0] << endl; return 0; }