結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | ctyl_0 |
提出日時 | 2015-10-04 18:26:39 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 28 ms / 5,000 ms |
コード長 | 3,206 bytes |
コンパイル時間 | 853 ms |
コンパイル使用メモリ | 93,708 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2024-07-19 19:34:55 |
合計ジャッジ時間 | 2,213 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <iostream> #include <iomanip> #include <vector> #include <algorithm> #include <numeric> #include <functional> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #define repd(i,a,b) for (int i=(a);i<(b);i++) #define rep(i,n) repd(i,0,n) #define mod 1000000007 typedef long long ll; using namespace std; int inputValue(){ int a; cin >> a; return a; }; template <typename T> void output(T a, int precision) { if(precision > 0){ cout << setprecision(precision) << a << "\n"; } else{ cout << a << "\n"; } } vector<vector<ll>> multi_mat(vector<vector<ll>> a, vector<vector<ll>> b, ll m){ vector<vector<ll>> ret(a.size(), vector<ll>(a.size(), 0)); rep(i, a.size()){ rep(j, a.size()){ rep(k, a.size()){ ret[i][j] = (ret[i][j] + a[i][k] * b[k][j]) % m; } } } return ret; } vector<vector<ll>> pow_mat(vector<vector<ll>> mat, ll pow, ll m){ vector<vector<ll>> ret(mat.size(), vector<ll>(mat.size(), 0)); rep(i, mat.size()){ ret[i][i] = 1; } while (pow > 0) { if (pow & 1) { ret = multi_mat(mat, ret, m); } mat = multi_mat(mat, mat, m); pow >>= 1; } return ret; } int main() { // source code int N; // 10^4, 30 ll K; // 10^6, 10^12 cin >> N >> K; vector<int> A(N); // 9 for (int i = 0; i < N; i++) { cin >> A[i]; } if (N > 30) { // #1 N > 30 vector<ll> S(K); // 10^6 S[0] = A[0]; repd(i, 1, N){ S[i] = (A[i] + S[i - 1]) % mod; } if (K >= N) { for (ll i = N; i < K; i++) { if (i == N) { S[i] = (2 * S[i - 1]) % mod; } else{ S[i] = (2 * S[i - 1] - S[i - (N + 1)] + mod) % mod; } } } cout << (S[K - 1] - S[K - 2] + mod) % mod << " "; cout << S[K - 1] << endl;// F(K), S(K) } else{ // #2 K large vector<ll> S(N); // 30 S[0] = A[0]; repd(i, 1, N){ S[i] = (A[i] + S[i - 1]) % mod; } if (N >= K) { cout << (S[K - 1] - S[K - 2] + mod) % mod << " "; cout << S[K - 1] << endl;// F(K), S(K) return 0; } // コンパニオン行列の作成 vector<vector<ll>> mat(N + 1, vector<ll>(N + 1)); rep(i, N + 1){ mat[0][i] = 1; } repd(i, 1, N + 1){ mat[1][i] = 1; } repd(i, 2, N + 1){ mat[i][i - 1] = 1; } vector<vector<ll>> ret = pow_mat(mat, K - N, mod); ll Sk = 0; ll Fk = 0; rep(i, N + 1){ if (i == 0) { Sk = (S[N - 1] * ret[0][0]) % mod; continue; } Sk = (Sk + A[N - i] * ret[0][i]) % mod; } repd(i, 1, N + 1){ Fk = (Fk + A[N - i] * ret[1][i]) % mod; } cout << Fk << " "; cout << Sk << endl; } return 0; }