結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー |
![]() |
提出日時 | 2015-05-01 16:18:32 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,643 bytes |
コンパイル時間 | 1,546 ms |
コンパイル使用メモリ | 166,440 KB |
実行使用メモリ | 11,180 KB |
最終ジャッジ日時 | 2024-07-05 17:21:55 |
合計ジャッジ時間 | 3,368 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 WA * 6 |
ソースコード
#include <bits/stdc++.h> #define rep(i, n) for (int (i) = 0; (i) < (int)(n); (i)++) const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, 1, 0, -1}; using namespace std; typedef long long ll; typedef long long number; typedef vector<number> vec; typedef vector<vec> matrix; const ll MOD = 1e9+7; // O( n ) matrix identity(int n) { matrix A(n, vec(n)); for (int i = 0; i < n; ++i) A[i][i] = 1; return A; } // O( n^3 ) matrix mul(const matrix &A, const matrix &B) { matrix C(A.size(), vec(B[0].size())); for (int i = 0; i < (int)C.size(); ++i) for (int j = 0; j < (int)C[i].size(); ++j) for (int k = 0; k < (int)A[i].size(); ++k) { C[i][j] += A[i][k] * B[k][j]; C[i][j] %= MOD; } return C; } // O( n^3 log e ) matrix pow(const matrix &A, ll e) { if (e == 0) return identity(A.size()); if (e == 1) return A; if (e % 2 == 0) { matrix tmp = pow(A, e/2); return mul(tmp, tmp); } else { matrix tmp = pow(A, e-1); return mul(A, tmp); } } const int MAXN = 10010; int A[MAXN]; ll F[1001010]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; ll K; cin >> N >> K; for (int i = 0; i < N; i++) cin >> A[i]; if (K > 1e6) { matrix B(2*N, vector<number>(2*N)); for (int i = 0; i < N; i++) { B[0][i] = 1; } for (int i = 0; i < N-1; i++) { B[i+1][i] = 1; } for (int i = 0; i < N; i++) { B[i+N][i] = 1; B[i+N][i+N] = 1; } B = pow(B, K-N); matrix C(2*N, vector<number>(N)); for (int i = 0; i < N; i++) C[i][i] = 1; C = mul(B, C); ll f = 0, s = 0; // f for (int i = 0; i < N; i++) { f += C[0][i] * A[N-1-i]; } f %= MOD; // s for (int i = 0; i < N; i++) { s += A[i]; } for (int i = 0; i < N; i++) { if (i == 0) s += (C[N][i]+C[0][i]-1) * A[N-1-i]; else s += (C[N][i]+C[0][i]) * A[N-1-i]; } s %= MOD; if (s < 0) s += MOD; cout << f << " " << s << endl; } else { ll sum = 0; for (int i = 0; i < N; i++) { F[i] = A[i]; sum += A[i]; } for (int i = N; i < K; i++) { F[i] = sum; sum += F[i]-F[i-N]; sum %= MOD; } sum = 0; for (int i = 0; i < K; i++) { sum += F[i]; sum %= MOD; } cout << F[K-1] << " " << sum << endl; } return 0; }