結果
問題 |
No.718 行列のできるフィボナッチ数列道場 (1)
|
ユーザー |
|
提出日時 | 2018-07-28 03:49:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 965 bytes |
コンパイル時間 | 2,048 ms |
コンパイル使用メモリ | 193,164 KB |
最終ジャッジ日時 | 2025-01-06 12:09:14 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
//================================= // Created on: 2018/07/28 03:44:33 //================================= #include <bits/stdc++.h> #define show(x) std::cerr << #x << " = " << x << std::endl using ll = long long; using V = std::array<ll, 2>; using M = std::array<V, 2>; constexpr ll MOD = 1e9 + 7; M mul(const M& m1, const M& m2) { M ans{{{0, 0}, {0, 0}}}; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { (ans[i][j] += m1[i][k] * m2[k][j]) %= MOD; } } } return ans; } M pow(const M& m, const ll n) { if (n == 0) { return M{{{1, 0}, {0, 1}}}; } if (n % 2 == 1) { return mul(pow(m, n - 1), m); } else { const auto pp = pow(m, n / 2); return mul(pp, pp); } } int main() { ll N; std::cin >> N; const M m{{{1, 1}, {1, 0}}}, mm = pow(m, N), mmm = mul(mm, m); std::cout << mm[0][1] * mmm[0][1] % MOD << std::endl; return 0; }