結果
問題 |
No.718 行列のできるフィボナッチ数列道場 (1)
|
ユーザー |
|
提出日時 | 2018-09-02 21:24:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,688 bytes |
コンパイル時間 | 1,953 ms |
コンパイル使用メモリ | 203,412 KB |
最終ジャッジ日時 | 2025-01-06 12:41:30 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename T> vector<vector<T>> mat_mul(vector<vector<T>> a, vector<vector<T>> b) { vector<vector<T>> c(a.size(), vector<T>(b[0].size())); for (int i = 0; i < a.size(); ++i) for (int j = 0; j < b.size(); ++j) for (int k = 0; k < b[j].size(); ++k) c[i][k] = c[i][k] + a[i][j] * b[j][k]; return c; } template<typename T> vector<vector<T>> mat_pow(vector<vector<T>> a, long long p) { vector<vector<T>> r(a.size(), vector<T>(a.size())); for (int i = 0; i < r.size(); ++i) r[i][i] = 1; for (; p; p >>= 1) { if (p & 1) r = mat_mul(r, a); a = mat_mul(a, a); } return r; } template <int mod> struct ModInt { int val; ModInt(int v = 0) : val((v % mod + mod) % mod) {} ModInt(long long v) : val((v % mod + mod) % mod) {} ModInt &operator=(int v) { return val = (v % mod + mod) % mod, *this; } ModInt &operator=(const ModInt &oth) { return val = oth.val, *this; } ModInt operator+(const ModInt &oth) const { int u = val + oth.val; return u < 0 ? u + mod : u; } ModInt operator*(const ModInt &oth) const { return 1LL * val * oth.val % mod; } ModInt operator-() const { return val > 0 ? mod - val : 0; } }; signed main() { const int M = int(1e9 + 7); long long N; cin >> N; vector<vector<ModInt<M>>> T = {{1, 1, 0, 0, 0}, {0, 1, 1, 2, 0}, {0, 1, 0, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 0, 1, 0}}; vector<vector<ModInt<M>>> A1 = {{1}, {1}, {1}, {1}, {0}}; cout << mat_mul(mat_pow(T, N - 1), A1)[0][0].val << endl; return 0; }