結果
問題 | 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;}