結果
問題 | No.194 フィボナッチ数列の理解(1) |
ユーザー | tnakao0123 |
提出日時 | 2016-03-26 19:40:41 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 18 ms / 5,000 ms |
コード長 | 2,951 bytes |
コンパイル時間 | 984 ms |
コンパイル使用メモリ | 92,588 KB |
実行使用メモリ | 19,328 KB |
最終ジャッジ日時 | 2024-10-02 00:56:04 |
合計ジャッジ時間 | 2,371 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
/* -*- coding: utf-8 -*- * * 194.cc: No.194 フィボナッチ数列の理解(1) - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 10000; const int MAX_K = 1000000; typedef long long ll; const ll MOD = 1000000007; /* typedef */ template <typename T> struct Vec { int n; vector<T> v; Vec() {} Vec(int _n): n(_n), v(_n, 0) {}; Vec(vector<T> _v): n(_v.size()), v(_v) {}; Vec(int _n, T _as[]): n(_n), v(_n) { for (int i = 0; i < n; i++) v[i] = _as[i]; } T& operator[](int i) { return v[i]; } void print() { for (int i = 0; i < n; i++) printf("%d ", v[i]); putchar('\n'); } }; template <typename T> struct Matrix { int n; vector<Vec<T> > m; Matrix() {} Matrix(int _n): n(_n), m(_n, Vec<T>(_n)) {}; void unit() { for (int i = 0; i < n; i++) m[i][i] = 1; } Vec<T>& operator[](int i) { return m[i]; } Matrix<T> operator*(Matrix<T>& m0) { Matrix<T> mm(n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { mm[i][j] = 0; for (int k = 0; k < n; k++) mm[i][j] = (mm[i][j] + m[i][k] * m0[k][j] % MOD) % MOD; } return mm; } Vec<T> operator*(Vec<T>& v0) { Vec<T> vv(n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) vv[i] = (vv[i] + m[i][j] * v0[j] % MOD) % MOD; return vv; } Matrix<T> pow(ll e) { Matrix<T> mm(n), m0 = *this; mm.unit(); while (e > 0) { if ((e & 1) != 0) mm = mm * m0; m0 = m0 * m0; e >>= 1; } return mm; } void trans() { for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) swap(m[i][j], m[j][i]); } void print() { for (int i = 0; i < n; i++) m[i].print(); } }; typedef Vec<ll> vec; typedef Matrix<ll> mat; /* global variables */ ll as[MAX_N]; ll fs[MAX_K], ss[MAX_K]; /* subroutines */ /* main */ int main() { int n; ll k; cin >> n >> k; for (int i = 0; i < n; i++) cin >> as[i]; fs[0] = ss[0] = as[0]; for (int i = 1; i < n; i++) { fs[i] = as[i]; ss[i] = (ss[i - 1] + fs[i]) % MOD; } fs[n] = ss[n - 1]; ss[n] = (ss[n - 1] + fs[n]) % MOD; if (k <= MAX_K) { int ki = k; for (int i = n + 1; i < ki; i++) { fs[i] = (ss[i - 1] + MOD - ss[i - n - 1]) % MOD; ss[i] = (ss[i - 1] + fs[i]) % MOD; } printf("%lld %lld\n", fs[ki - 1], ss[ki - 1]); } else { mat sm(n + 1); for (int i = 0; i < n; i++) sm[i][i + 1] = 1; sm[n][0] = MOD - 1, sm[n][n] = 2; mat pm = sm.pow(k - n - 1); vec sv(n + 1, ss); vec v = pm * sv; ll fk = (v[n] + MOD - v[n - 1]) % MOD; ll sk = v[n]; printf("%lld %lld\n", fk, sk); } return 0; }