結果
問題 |
No.718 行列のできるフィボナッチ数列道場 (1)
|
ユーザー |
![]() |
提出日時 | 2018-08-28 09:43:46 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,255 bytes |
コンパイル時間 | 701 ms |
コンパイル使用メモリ | 82,372 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-07 14:02:10 |
合計ジャッジ時間 | 1,620 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <stack> #include <queue> #include <map> #include <unordered_map> #include <cassert> using namespace std; using i64 = int64_t; constexpr i64 mod = 1e9 + 7; using vi = vector<i64>; using vvi = vector<vi>; using ii = pair<i64, i64>; using vii = vector<ii>; struct mat { i64 a, b, c, d, e, f, g, h, i; mat operator*(const mat m) { return { (a * m.a + b * m.d + c * m.g) % mod, (a * m.b + b * m.e + c * m.h) % mod, (a * m.c + b * m.f + c * m.i) % mod, (d * m.a + e * m.d + f * m.g) % mod, (d * m.b + e * m.e + f * m.h) % mod, (d * m.c + e * m.f + f * m.i) % mod, (g * m.a + h * m.d + i * m.g) % mod, (g * m.b + h * m.e + i * m.h) % mod, (g * m.c + h * m.f + i * m.i) % mod }; } }; mat matpow(mat m, i64 n) { if (n == 0) { return {1,0,0,0,1,0,0,0,1}; } if (n % 2 == 0) { mat tmp = matpow(m, n / 2); return tmp * tmp; } return m * matpow(m, n - 1); } int main() { i64 n; cin >> n; mat m = matpow({1,2,1,1,1,0,1,0,0}, n - 1); cout << (m.d + m.e + m.f) % mod << endl; }