結果

問題 No.194 フィボナッチ数列の理解(1)
ユーザー r_dream0r_dream0
提出日時 2017-02-09 00:19:16
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 18 ms / 5,000 ms
コード長 2,974 bytes
コンパイル時間 671 ms
コンパイル使用メモリ 66,948 KB
実行使用メモリ 16,572 KB
最終ジャッジ日時 2024-06-07 13:13:30
合計ジャッジ時間 1,889 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

const int64_t MOD = 1000000007;
void next(vector<long> &x, const vector<long> &first, long MOD) {
  long last = x.back();
  for(int i = x.size() - 2;  i >= 0 ; i--) x[i + 1] = x[i];
  x[0] = 0;
  if(last == 500000004) last = 333333331;
  for(int i = 0; i < x.size(); i++) x[i] = (MOD + x[i] - (long)last * first[i] % MOD) % MOD;
}

vector<long> next2N(const vector<long> &x, const vector<long> &first, long MOD) {
  vector<long> tmp(x);
  vector<long> result(x.size());
  for(int i = 0; i < x.size(); i++) {
    for(int j = 0; j < tmp.size(); j++) {
      result[j] = (result[j] + MOD - x[i] * tmp[j]) % MOD;
    }
    next(tmp, first, MOD);
  }
  return result;
}
long calc(const vector<long> &poly, const vector<long> &x, long MOD, int ofs = 0) {
  __int128_t ret = 0;
  for(int i = 0; i < poly.size(); i++) {
    ret += x[i + ofs] * poly[i] % MOD;
    ret %= MOD;
  }
  return (MOD - ret) % MOD;
}
long kitamasa(const vector<long> &poly, const vector<long> &x, int64_t N, long MOD) {
  if(N < poly.size()) return x[N];
  int t = poly.size(), l = 0;
  while(t > 0) t >>= 1, l++;
  for(int i = 0; i <= l; i++) {
    if(N >> (63 - __builtin_clzl(N) - l + i) & 1) {
      t |= 1LL << i;
    }
  }
  long cur = poly.size();
  vector<long> curPoly = poly;
  vector<long> poy2 = poly;
  while(cur < t) {
    if(cur == N) {
      return calc(curPoly, x, MOD);
    }
    next(curPoly, poly, MOD);
    cur++;
  }
  vector<long> ret(curPoly.size());
  cur = 0;
  for(int i = 63 - __builtin_clzl(N) - l - 1; i >= 0; i--) {
    curPoly = next2N(curPoly, poly, MOD);
    if(N >> i & 1) next(curPoly, poly, MOD);
  }
  return calc(curPoly, x, MOD);
}

int main() {
  int64_t N, K;
  cin >> N >> K;
  vector<int64_t> A(N);
  for(auto &t: A) cin >> t;
  if(K <= 1000000) {
    A.push_back(accumulate(A.begin(), A.end(), 0LL) % MOD);
    while(A.size() < K) {
      A.push_back((A.back() * 2 + MOD - A[A.size() - N - 1]) % MOD);
    }
    cout << A.back() << " " << accumulate(A.begin(), A.end(), 0LL) % MOD << endl;
  } else {
    A.push_back(accumulate(A.begin(), A.end(), 0LL) % MOD);
    while(A.size() < N + 2) {
      A.push_back((A.back() * 2 + MOD - A[A.size() - N - 1]) % MOD);
    }
    vector<int64_t> poly(N, MOD-1), poly2(N + 1, MOD-1), retpoly(N + 2, 0);
    poly2[N] = 1;
    // x - 1を掛ける
    for(int i = 0; i < N + 1; i++) {
      retpoly[i + 1] += poly2[i];
      retpoly[i] = (retpoly[i] + (MOD - 1) * poly2[i]) % MOD;
    }
    // x + 1をかける
    poly2 = retpoly;
    retpoly = vector<int64_t>(N + 3);
    for(int i = 0; i < N + 2; i++) {
      retpoly[i + 1] += poly2[i];
      retpoly[i] = (retpoly[i] + poly2[i]) % MOD;
    }
    poly2 = retpoly;
    vector<int64_t> B(A);
    for(int i = 1; i < N + 2; i++) {
      B[i] = (B[i - 1] + A[i]) % MOD;
    }

    poly2.pop_back();
    cout << kitamasa(poly, A, K - 1, MOD) << " " << kitamasa(poly2, B, K - 1, MOD) << endl;
  }
}
0