結果

問題 No.194 フィボナッチ数列の理解(1)
コンテスト
ユーザー r_dream0
提出日時 2017-02-09 00:19:16
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 27 ms / 5,000 ms
コード長 2,974 bytes
コンパイル時間 981 ms
コンパイル使用メモリ 66,624 KB
実行使用メモリ 15,720 KB
最終ジャッジ日時 2024-12-25 17:01:16
合計ジャッジ時間 2,256 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

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