結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー |
![]() |
提出日時 | 2020-12-15 19:19:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 15 ms / 5,000 ms |
コード長 | 1,841 bytes |
コンパイル時間 | 3,772 ms |
コンパイル使用メモリ | 201,572 KB |
最終ジャッジ日時 | 2025-01-17 01:09:39 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1e9 + 7; void inc(const vector<ll>& A, const vector<ll>& B, vector<ll>& res, const ll MOD) { int N = (int)A.size(); res[0] = (B[N - 1] * A[0]) % MOD; for (int i = 1; i < N; i++) { res[i] = (B[i - 1] + B[N - 1] * A[i]) % MOD; } }; vector<ll> kitamasa(const vector<ll>& A, ll K, const ll MOD) { int N = (int)A.size(); vector<vector<ll>> C(N, vector<ll>(N)); vector<ll> ret(N, 0); ret[0] = 1; int cnt = 63; while (((K >> --cnt) & 1) == 0) ; cnt++; while (cnt-- > 0) { C[0] = ret; for (int i = 0; i < N - 1; i++) { inc(A, C[i], C[i + 1], MOD); } for (int i = 0; i < N; i++) { ret[i] = 0; for (int j = 0; j < N; j++) { (ret[i] += (C[0][j] * C[j][i])) %= MOD; } } if ((K >> cnt) & 1) { inc(A, ret, C[0], MOD); ret = C[0]; } } return ret; } int main() { int N; ll K; cin >> N >> K; vector<ll> A(N + 1); for (int i = 0; i < N; i++) { cin >> A[i + 1]; A[i + 1] += A[i]; } if (N > 30) { A.resize(K + 10); for (int i = N; i < K + 5; i++) { A[i + 1] = (A[i] * 2 - A[i - N] + MOD) % MOD; } cout << (A[K] - A[K - 1] + MOD) % MOD << " " << A[K] << endl; exit(0); } vector<ll> R(N + 1, 0); R[0] = MOD - 1; R[N] = 2; auto V = kitamasa(R, K, MOD); ll FK1 = 0; for (int i = 0; i < N + 1; i++) { (FK1 += V[i] * A[i]) %= MOD; } V = kitamasa(R, K - 1, MOD); ll FK0 = 0; for (int i = 0; i < N + 1; i++) { (FK0 += V[i] * A[i]) %= MOD; } cout << (FK1 - FK0 + MOD) % MOD << " " << FK1 << endl; }