結果

問題 No.2580 Hyperinflation
ユーザー 👑 tute7627tute7627
提出日時 2023-12-08 21:46:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,382 bytes
コンパイル時間 8,871 ms
コンパイル使用メモリ 413,808 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-27 03:10:34
合計ジャッジ時間 10,675 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 WA -
testcase_15 AC 3 ms
5,376 KB
testcase_16 WA -
testcase_17 AC 2 ms
5,376 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

// https://atcoder.jp/contests/arc118/submissions/24453032

#include <bits/stdc++.h>

#include <atcoder/convolution>

using Fp = atcoder::modint998244353;
std::ostream& operator<<(std::ostream& os, Fp a) { return os << a.val(); }

using Fps = std::vector<Fp>;
int sz(const Fps& a) { return a.size(); }
Fps operator-(Fps a) {
  for (auto&& e : a) e = -e;
  return a;
}
Fps& operator+=(Fps& a, const Fps& b) {
  if (sz(a) < sz(b)) a.reserve(sz(b)), a.resize(sz(b));
  for (int i = 0; i < sz(b); ++i) a[i] += b[i];
  return a;
}
Fps operator+(Fps a, const Fps& b) { return std::move(a += b); }
Fps& operator-=(Fps& a, const Fps& b) {
  if (sz(a) < sz(b)) a.reserve(sz(b)), a.resize(sz(b));
  for (int i = 0; i < sz(b); ++i) a[i] -= b[i];
  return a;
}
Fps operator-(Fps a, const Fps& b) { return std::move(a -= b); }
Fps& operator*=(Fps& a, Fp b) {
  for (auto&& e : a) e *= b;
  return a;
}
Fps operator*(Fps a, Fp b) { return std::move(a *= b); }
Fps operator*(Fp a, Fps b) { return std::move(b *= a); }
Fps& operator/=(Fps& a, Fp b) {
  b = b.inv();
  for (auto&& e : a) e *= b;
  return a;
}
Fps operator/(Fps a, Fp b) { return std::move(a /= b); }
Fps fft(const Fps& a, int n) {
  Fps res(n);
  std::copy(a.begin(), a.begin() + std::min(n, sz(a)), res.begin());
  atcoder::internal::butterfly(res);
  return res;
}
Fps circ(Fps&& a, const Fps& b) {
  if (sz(a) < sz(b)) a.reserve(sz(b)), a.resize(sz(b));
  for (int i = 0; i < sz(b); ++i) a[i] *= b[i];
  return a;
}
Fps circ(Fps&& a) {
  for (auto&& e : a) e *= e;
  return a;
}
Fps ifft(Fps&& a, int size) {
  int n = sz(a);
  atcoder::internal::butterfly_inv(a);
  a.resize(size);
  a *= (1 - Fp::mod()) / n;
  return a;
}
Fps operator*(const Fps& a, const Fps& b) {
  if (a.empty() || b.empty()) return {};
  if (std::min(sz(a), sz(b)) <= 60) {
    Fps res(std::max(sz(a), sz(b)));
    for (int i = 0; i < sz(a); ++i)
      for (int j = 0; j < sz(b); ++j) {
        if (i + j == sz(res)) break;
        res[i + j] += a[i] * b[j];
      }
    return res;
  }
  int n = 1 << atcoder::internal::bit_ceil(sz(a) + sz(b) - 1);
  auto buf = fft(a, n);
  if (&a == &b)
    buf = circ(std::move(buf));
  else
    buf = circ(std::move(buf), fft(b, n));
  return ifft(std::move(buf), std::max(sz(a), sz(b)));
}
Fps& operator*=(Fps& a, const Fps& b) { return a = a * b; }
Fps inv(const Fps& a) {
  Fps res{a[0].inv()};
  for (int n = 1; n < sz(a); n *= 2) {
    auto f_res = fft(res, 2 * n);
    Fps buf = ifft(circ(fft(a, 2 * n), f_res), 2 * n);
    std::fill(buf.begin(), buf.begin() + n, 0);
    buf = ifft(circ(fft(buf, 2 * n), f_res), std::min(2 * n, sz(a)));
    for (int i = n; i < sz(buf); ++i) res.push_back(-buf[i]);
  }
  return res;
}

using Poly = std::vector<Fp>;
Fp eval(const Poly& a, Fp x) {
  Fp res;
  for (int i = sz(a); i--;) (res *= x) += a[i];
  return res;
}

std::vector<Fp> fact, ifact;
void reserve(int n) {
  fact.resize(n + 1), ifact.resize(n + 1);
  fact[0] = 1;
  for (int i = 1; i <= n; ++i) fact[i] = i * fact[i - 1];
  ifact[n] = fact[n].pow(Fp::mod() - 2);
  for (int i = n; i; --i) ifact[i - 1] = ifact[i] * i;
}

using namespace std;

#include<boost/multiprecision/cpp_int.hpp>

int main() {
  using namespace std;
  cin.tie(nullptr)->sync_with_stdio(false);
  using bigint=boost::multiprecision::cpp_int;
  int n;
  bigint m;
  cin >> n;n--;
  vector<int> a(n);
  bigint mult = 1;
  for (auto&& e : a){
    cin >> e;
    mult *= bigint(e);
  }
  reverse(a.begin(),a.end());
  cin >> m;
  m += mult;
  reserve(n + 1);
  auto calc=[&](bigint m){
    Fps bernoulli(n + 1);
    for (int i = 0; i <= n; ++i) bernoulli[i] = ifact[i + 1];
    bernoulli = inv(bernoulli);
    auto faulhaber = [&](Poly f) -> Poly {
      for (int i = 0; i < sz(f); ++i) f[i] *= fact[i];
      reverse(begin(f), end(f));
      f *= Fps(begin(bernoulli), begin(bernoulli) + sz(f));
      f.push_back(0);
      reverse(begin(f), end(f));
      for (int i = 0; i < sz(f); ++i) f[i] *= ifact[i];
      return f;
    };
    Poly f{1};
    for (int i = n; i--;) {
      Poly g = faulhaber(f);
      f = -g;
      Fp coeff = 1;
      for (int j = 1; j < sz(f); ++j) f[j] *= coeff *= a[i];
      f[0] = eval(g, static_cast<int>((m + 1)%bigint(998244353)));
      m /= bigint(a[i]);
    }
    f = faulhaber(f);
    return eval(f,static_cast<int> ((m + 1)%bigint(998244353))) - eval(f, 1);
  };
  cout << calc(m) - calc(m-1) << '\n';
}
0