結果

問題 No.194 フィボナッチ数列の理解(1)
ユーザー tnakao0123tnakao0123
提出日時 2016-03-26 19:40:41
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 18 ms / 5,000 ms
コード長 2,951 bytes
コンパイル時間 720 ms
コンパイル使用メモリ 93,684 KB
実行使用メモリ 19,172 KB
最終ジャッジ日時 2024-04-09 23:59:00
合計ジャッジ時間 2,219 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 9 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 4 ms
6,944 KB
testcase_05 AC 4 ms
6,944 KB
testcase_06 AC 5 ms
6,940 KB
testcase_07 AC 7 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 6 ms
6,940 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 3 ms
6,940 KB
testcase_12 AC 4 ms
6,944 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 8 ms
6,940 KB
testcase_16 AC 7 ms
6,944 KB
testcase_17 AC 3 ms
6,940 KB
testcase_18 AC 8 ms
6,944 KB
testcase_19 AC 9 ms
6,944 KB
testcase_20 AC 15 ms
19,080 KB
testcase_21 AC 18 ms
19,132 KB
testcase_22 AC 15 ms
19,172 KB
testcase_23 AC 4 ms
6,944 KB
testcase_24 AC 10 ms
13,664 KB
testcase_25 AC 9 ms
11,236 KB
testcase_26 AC 9 ms
14,236 KB
testcase_27 AC 9 ms
13,908 KB
testcase_28 AC 4 ms
8,560 KB
testcase_29 AC 14 ms
18,488 KB
testcase_30 AC 9 ms
6,940 KB
testcase_31 AC 1 ms
6,940 KB
testcase_32 AC 4 ms
6,944 KB
testcase_33 AC 5 ms
6,944 KB
testcase_34 AC 5 ms
6,940 KB
testcase_35 AC 4 ms
6,944 KB
testcase_36 AC 8 ms
6,944 KB
testcase_37 AC 3 ms
6,944 KB
testcase_38 AC 9 ms
6,944 KB
testcase_39 AC 4 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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