結果
問題 | No.534 フィボナッチフィボナッチ数 |
ユーザー |
![]() |
提出日時 | 2020-11-29 05:54:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,588 bytes |
コンパイル時間 | 1,084 ms |
コンパイル使用メモリ | 73,492 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-13 01:52:42 |
合計ジャッジ時間 | 2,139 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
#include <iostream> #include <vector> using namespace std; using ll = long long int; const ll MOD = 1000'000'007; vector<vector<ll>> update(vector<vector<ll>> &matrix, ll mod){ vector<vector<ll>> ans(matrix.size(), vector<ll>(matrix.size(), 0)); for(int i = 0; i < matrix.size(); i++){ for(int j = 0; j < matrix.size(); j++){ for(int k = 0; k < matrix.size(); k++){ ans[i][j] += matrix[i][k]*matrix[k][j]; ans[i][j] %= mod; } } } return ans; } vector<ll> times(vector<ll> &memo, vector<vector<ll>> &matrix, ll mod){ vector<ll> ans(memo.size(), 0); for(int i = 0; i < memo.size(); i++){ for(int j = 0; j < memo.size(); j++){ ans[i] += memo[j]*matrix[i][j]; ans[i] %= mod; } } return ans; } vector<ll> matpow(vector<ll> &memo, vector<vector<ll>> &matrix, ll n, ll mod){ vector<ll> ans = memo; while(n){ if(n & 1){ ans = times(ans, matrix, mod); } matrix = update(matrix, mod); n >>= 1; } return ans; } int main(){ ll n; cin >> n; vector<vector<ll>> matrix(2, vector<ll>(2)); vector<ll> memo(2); matrix[0][0] = matrix[0][1] = matrix[1][0] = 1; matrix[1][1] = 0; memo[0] = 1; memo[1] = 0; memo = matpow(memo, matrix, n, (MOD+1)*2); ll fn = memo[1]; matrix[0][0] = matrix[0][1] = matrix[1][0] = 1; matrix[1][1] = 0; memo[0] = 1; memo[1] = 0; memo = matpow(memo, matrix, fn, MOD); cout << memo[1] << endl; return 0; }