結果
問題 |
No.720 行列のできるフィボナッチ数列道場 (2)
|
ユーザー |
|
提出日時 | 2018-07-28 00:41:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 2,000 ms |
コード長 | 1,131 bytes |
コンパイル時間 | 2,164 ms |
コンパイル使用メモリ | 192,440 KB |
最終ジャッジ日時 | 2025-01-06 12:08:15 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
//================================= // Created on: 2018/07/28 00:18:13 //================================= #include <bits/stdc++.h> #define show(x) std::cerr << #x << " = " << x << std::endl using ll = long long; constexpr ll MOD = 1000000007LL; using V = std::array<ll, 4>; using M = std::array<V, 4>; M mul(const M& m1, const M& m2) { M ans{{{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}}; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { for (int k = 0; k < 4; 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, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 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, MM; std::cin >> N >> MM; M m{{{1, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}}; m = pow(m, MM); m[2][0] = m[2][2] = m[3][1] = m[3][3] = 1; m = pow(m, N + 1); std::cout << m[2][1] << std::endl; return 0; }