結果

問題 No.194 フィボナッチ数列の理解(1)
コンテスト
ユーザー tnakao0123
提出日時 2016-03-26 19:40:41
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 18 ms / 5,000 ms
コード長 2,951 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 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 #
raw source code 

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