結果
問題 | No.534 フィボナッチフィボナッチ数 |
ユーザー |
|
提出日時 | 2017-07-01 19:07:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,601 bytes |
コンパイル時間 | 1,149 ms |
コンパイル使用メモリ | 109,376 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-05 00:01:12 |
合計ジャッジ時間 | 2,370 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
#define _USE_MATH_DEFINES#include <cstdio>#include <iostream>#include <sstream>#include <fstream>#include <iomanip>#include <algorithm>#include <cmath>#include <complex>#include <string>#include <vector>#include <list>#include <queue>#include <stack>#include <set>#include <map>#include <bitset>#include <numeric>#include <limits>#include <climits>#include <cfloat>#include <functional>#include <iterator>using namespace std;template <class T>vector<vector<T> > matrixProduct(const vector<vector<T> >& x, const vector<vector<T> >& y, int mod){int a = x.size();int b = x[0].size();int c = y[0].size();vector<vector<T> > z(a, vector<T>(c, 0));for(int i=0; i<a; ++i){for(int j=0; j<c; ++j){for(int k=0; k<b; ++k){z[i][j] += x[i][k] * y[k][j];z[i][j] %= mod;}}}return z;}template <class T>vector<vector<T> > matrixPower(const vector<vector<T> >& x, long long k, int mod){int n = x.size();vector<vector<T> > y(n, vector<T>(n, 0));for(int i=0; i<n; ++i)y[i][i] = 1; // 積の単位元vector<vector<T> > z = x;while(k > 0){if(k & 1)y = matrixProduct(y, z, mod);z = matrixProduct(z, z, mod);k >>= 1;}return y;}const int MOD = 1000000007;int main(){long long n;cin >> n;vector<vector<long long> > mat = {{1,1}, {1,0}};auto a = matrixPower(mat, n, MOD*2+2);auto b = matrixPower(mat, a[0][1], MOD);cout << b[0][1] << endl;return 0;}