結果

問題 No.137 貯金箱の焦り
コンテスト
ユーザー applejam
提出日時 2025-12-14 15:55:24
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 7,852 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,616 ms
コンパイル使用メモリ 335,640 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-14 15:57:01
合計ジャッジ時間 96,857 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other AC * 10 WA * 2 TLE * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vmi = vector<mint>;
using vvmi = vector<vmi>;
using vvvmi = vector<vvmi>;
#define all(a) (a).begin(), (a).end()
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)

template<class T>
struct FormalPowerSeries : vector<T> {
  using vector<T>::vector;
  using vector<T>::operator=;
  using F = FormalPowerSeries;

  F operator-() const {
    F res(*this);
    for (auto &e : res) e = -e;
    return res;
  }
  F &operator*=(const T &g) {
    for (auto &e : *this) e *= g;
    return *this;
  }
  F &operator/=(const T &g) {
    assert(g != T(0));
    *this *= g.inv();
    return *this;
  }
  F &operator+=(const F &g) {
    int n = (*this).size(), m = g.size();
    rep(i, min(n, m)) (*this)[i] += g[i];
    return *this;
  }
  F &operator-=(const F &g) {
    int n = (*this).size(), m = g.size();
    rep(i, min(n, m)) (*this)[i] -= g[i];
    return *this;
  }
  F &operator<<=(const int d) {
    int n = (*this).size();
    (*this).insert((*this).begin(), d, 0);
    (*this).resize(n);
    return *this;
  }
  F &operator>>=(const int d) {
    int n = (*this).size();
    (*this).erase((*this).begin(), (*this).begin() + min(n, d));
    (*this).resize(n);
    return *this;
  }
  F inv(int d = -1) const {
    int n = (*this).size();
    assert(n != 0 && (*this)[0] != 0);
    if (d == -1) d = n;
    assert(d > 0);
    F res{(*this)[0].inv()};
    while (res.size() < d) {
      int m = size(res);
      F f(begin(*this), begin(*this) + min(n, 2*m));
      F r(res);
      f.resize(2*m), internal::butterfly(f);
      r.resize(2*m), internal::butterfly(r);
      rep(i, 2*m) f[i] *= r[i];
      internal::butterfly_inv(f);
      f.erase(f.begin(), f.begin() + m);
      f.resize(2*m), internal::butterfly(f);
      rep(i, 2*m) f[i] *= r[i];
      internal::butterfly_inv(f);
      T iz = T(2*m).inv(); iz *= -iz;
      rep(i, m) f[i] *= iz;
      res.insert(res.end(), f.begin(), f.begin() + m);
    }
    return {res.begin(), res.begin() + d};
  }

  // // fast: FMT-friendly modulus only
  /*F &operator*=(const F &g) {
    int n = (*this).size();
     *this = convolution(*this, g);
     (*this).resize(n);
     return *this;
   }
   F &operator/=(const F &g) {
     int n = (*this).size();
     *this = convolution(*this, g.inv(n));
     (*this).resize(n);
     return *this;
   }*/

  // // naive
   F &operator*=(const F &g) {
     int n = (*this).size(), m = g.size();
     drep(i, n) {
       (*this)[i] *= g[0];
       rep2(j, 1, min(i+1, m)) (*this)[i] += (*this)[i-j] * g[j];
     }
     return *this;
   }
   F &operator/=(const F &g) {
     assert(g[0] != T(0));
     T ig0 = g[0].inv();
     int n = (*this).size(), m = g.size();
     rep(i, n) {
       rep2(j, 1, min(i+1, m)) (*this)[i] -= (*this)[i-j] * g[j];
       (*this)[i] *= ig0;
     }
     return *this;
   }

  // sparse
  F &operator*=(vector<pair<int, T>> g) {
    int n = (*this).size();
    auto [d, c] = g.front();
    if (d == 0) g.erase(g.begin());
    else c = 0;
    drep(i, n) {
      (*this)[i] *= c;
      for (auto &[j, b] : g) {
        if (j > i) break;
        (*this)[i] += (*this)[i-j] * b;
      }
    }
    return *this;
  }
  F &operator/=(vector<pair<int, T>> g) {
    int n = (*this).size();
    auto [d, c] = g.front();
    assert(d == 0 && c != T(0));
    T ic = c.inv();
    g.erase(g.begin());
    rep(i, n) {
      for (auto &[j, b] : g) {
        if (j > i) break;
        (*this)[i] -= (*this)[i-j] * b;
      }
      (*this)[i] *= ic;
    }
    return *this;
  }

  // multiply and divide (1 + cz^d)
  void multiply(const int d, const T c) { 
    int n = (*this).size();
    if (c == T(1)) drep(i, n-d) (*this)[i+d] += (*this)[i];
    else if (c == T(-1)) drep(i, n-d) (*this)[i+d] -= (*this)[i];
    else drep(i, n-d) (*this)[i+d] += (*this)[i] * c;
  }
  void divide(const int d, const T c) {
    int n = (*this).size();
    if (c == T(1)) rep(i, n-d) (*this)[i+d] -= (*this)[i];
    else if (c == T(-1)) rep(i, n-d) (*this)[i+d] += (*this)[i];
    else rep(i, n-d) (*this)[i+d] -= (*this)[i] * c;
  }

  T eval(const T &a) const {
    T x(1), res(0);
    for (auto e : *this) res += e * x, x *= a;
    return res;
  }

  F diff() const {
    int n = (int)this->size();
    if (n == 0) return F{};
    F res(n);
    for (int i = 1; i < n; i++) res[i-1] = (*this)[i] * T(i);
    res[n-1] = T(0);
    return res;
    }

F integral() const {
    int n = (int)this->size();
    F res(n);
    res[0] = T(0);
    for (int i = 0; i + 1 < n; i++) res[i+1] = (*this)[i] / T(i+1);
    return res;
}

F log() const {
  int n = (int)this->size();
  assert(n > 0 && (*this)[0] == T(1));
  F f = *this;
  F res = (f.diff() / f).integral();
  res.resize(n);
  return res;
}

F exp() const {
  int n = (int)this->size();
  assert(n > 0 && (*this)[0] == T(0));

  F f = *this;

  F g(n);            // g = 1
  g[0] = T(1);

  int m = 1;
  while (m < n) {
    int k = min(n, 2*m);

    // g_k = g mod x^k
    F gk = g;
    gk.resize(k);

    // log(gk) mod x^k
    F lg = gk.log();        // requires gk[0]==1 OK

    // h = f - log(g)  (mod x^k)
    F h(k);
    for (int i = 0; i < k; i++) {
      T fi = (i < (int)f.size() ? f[i] : T(0));
      T lgi = (i < (int)lg.size() ? lg[i] : T(0));
      h[i] = fi - lgi;
    }
    h[0] += T(1);            // 1 + f - log(g)

    // g <- g * h  (mod x^k)
    gk *= h;                 // operator*= does convolution and resizes to k (since gk.size()==k)
    gk.resize(k);

    // write back
    for (int i = 0; i < k; i++) g[i] = gk[i];
    m <<= 1;
  }
  g.resize(n);
  return g;
}

F neg_x(const F& Q){
  F R = Q;
  for(int i=1;i<(int)R.size();i+=2) R[i] = -R[i];
  return R;
}

F even_part(const F& A){
  int n = (int)A.size();
  F E((n+1)/2);
  for(int i=0;i<n;i+=2) E[i/2]=A[i];
  return E;
}

F odd_part(const F& A){
  int n = (int)A.size();
  F O(n/2);
  for(int i=1;i<n;i+=2) O[i/2]=A[i];
  return O;
}

T bostan_mori(F P, F Q, long long m){
  // normalize if you want: ensure Q[0]=1 by dividing both by Q[0]
  assert(Q.size()>0 && Q[0]!=T(0));

  while(m>0){
    int d = (int)Q.size()-1;
    int need = 2*d + 1;              // enough degrees
    P.resize(need);
    Q.resize(need);

    F Qm = neg_x(Q);

    F A = P; A *= Qm;                // A = P*Q(-x) mod x^need
    F B = Q; B *= Qm;                // B = Q*Q(-x) mod x^need

    if((m&1)==0){
      P = even_part(A);
    }else{
      P = odd_part(A);
    }
    Q = even_part(B);
    m >>= 1;
  }
  return P[0] / Q[0];
}

  F operator*(const T &g) const { return F(*this) *= g; }
  F operator/(const T &g) const { return F(*this) /= g; }
  F operator+(const F &g) const { return F(*this) += g; }
  F operator-(const F &g) const { return F(*this) -= g; }
  F operator<<(const int d) const { return F(*this) <<= d; }
  F operator>>(const int d) const { return F(*this) >>= d; }
  F operator*(const F &g) const { return F(*this) *= g; }
  F operator/(const F &g) const { return F(*this) /= g; }
  F operator*(vector<pair<int, T>> g) const { return F(*this) *= g; }
  F operator/(vector<pair<int, T>> g) const { return F(*this) /= g; }
};

using fps = FormalPowerSeries<mint>;
using sfps = vector<pair<int, mint>>;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    mint::set_mod(1234567891);
    int n; ll m; cin >> n >> m;
    fps f = {1}; f.resize(3000);
    rep(i, n){
        int a; cin >> a;
        f.multiply(a, -1);
    }
    fps g = {1};
    cout << g.bostan_mori(g, f, m).val() << endl;

    return 0;
}
0