結果

問題 No.194 フィボナッチ数列の理解(1)
ユーザー tnakao0123tnakao0123
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/* -*- 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0