結果

問題 No.2579 Dice Sum Infinity (制約変更版)
コンテスト
ユーザー noshi91
提出日時 2023-04-29 05:09:51
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 647 ms / 6,000 ms
コード長 7,062 bytes
コンパイル時間 9,561 ms
コンパイル使用メモリ 164,008 KB
最終ジャッジ日時 2025-02-12 15:53:02
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("bmi,lzcnt")

#include <cassert>
#include <utility>
#include <vector>

#ifndef NOSHI91_POLYNOMIAL_INTERNAL
#define NOSHI91_POLYNOMIAL_INTERNAL

#include <vector>

#include <atcoder/convolution>

namespace noshi91 {

namespace polynomial {

namespace internal {

template <class T> const atcoder::internal::fft_info<T> info;

template <class T> void dft(std::vector<T> &a) {
  atcoder::internal::butterfly(a);
}

template <class T> void inv_dft(std::vector<T> &a) {
  atcoder::internal::butterfly_inv(a);
  T c = T::mod() - (T::mod() - 1) / a.size();
  for (auto &e : a)
    e *= c;
}

template <class T>
std::vector<T> convolution(std::vector<T> a, std::vector<T> b, int cyc_limit) {
  assert(a.size() <= cyc_limit);
  assert(b.size() <= cyc_limit);
  if (cyc_limit == 0)
    return a;
  cyc_limit = 1 << (31 - __builtin_clz(2 * cyc_limit - 1));
  a.resize(cyc_limit), dft(a);
  b.resize(cyc_limit), dft(b);
  for (int i = 0; i < cyc_limit; i++)
    a[i] *= b[i];
  inv_dft(a);
  return a;
}

} // namespace internal

} // namespace polynomial

} // namespace noshi91

#endif

namespace noshi91 {

namespace polynomial {

namespace shifted_rev_inverse_internal {

using ll = long long;

// [x^[-d,0)] x^k / f  in K((x^{-1}))
template <class T> std::vector<T> shifted_rev_inverse(std::vector<T> f, ll k) {
  assert(!f.empty() && f.back() != 0);
  assert(k >= 0);
  const T h = 1 / f.back();
  for (T &c : f)
    c *= h;
  f.pop_back();
  const int n_ = f.size();
  if (n_ == 0)
    return {};
  const int rank = 31 - __builtin_clz(2 * n_ - 1);
  const T w = internal::info<T>.root[rank + 1];
  const int n = 1 << rank;
  const int pad = n - n_;
  k += pad;
  f.insert(f.begin(), pad, 0);
  f[0] += 1;
  internal::dft(f);
  const auto rec = [&](const auto &rec, std::vector<T> f,
                       ll k) -> std::vector<T> {
    if (k == 0) {
      std::vector<T> ret(n);
      ret[0] = 1;
      return ret;
    }
    std::vector<T> g(2 * n);
    std::copy(f.begin(), f.end(), g.begin());
    internal::inv_dft(f);
    f[0] -= 2;
    T r = 1;
    for (int i = 0; i < n; i++)
      f[i] *= r, r *= w;
    internal::dft(f);
    std::copy(f.begin(), f.end(), g.begin() + n);
    for (int i = 0; i < n; i++) {
      f[i] = g[i * 2] * g[i * 2 + 1];
      std::swap(g[i * 2], g[i * 2 + 1]);
    }
    std::vector<T> res = rec(rec, std::move(f), k / 2);
    internal::dft(res);
    res.resize(2 * n);
    if (k & 1) {
      r = 1;
      for (int i = 0; i < n; i++)
        res[i] *= r, r *= internal::info<T>.rate2[__builtin_ctz(~i)];
      for (int i = n; i-- > 0;) {
        res[i * 2 + 1] = -res[i];
        res[i * 2] = res[i];
      }
    } else {
      for (int i = n; i-- > 0;) {
        res[i * 2 + 1] = res[i];
        res[i * 2] = res[i];
      }
    }
    for (int i = 0; i < 2 * n; i++)
      res[i] *= g[i];
    internal::inv_dft(res);
    res.erase(res.begin(), res.begin() + n);
    return res;
  };
  std::vector<T> ret = rec(rec, std::move(f), k);
  ret.erase(ret.begin(), ret.begin() + pad);
  for (T &c : ret)
    c *= h;
  return ret;
}

} // namespace shifted_rev_inverse_internal

using shifted_rev_inverse_internal::shifted_rev_inverse;

} // namespace polynomial

} // namespace noshi91

#include <cassert>
#include <utility>
#include <vector>

namespace noshi91 {

namespace polynomial {

template <class T>
std::vector<T> modular_inverse(std::vector<T> f, std::vector<T> m) {
  assert(!m.empty() && m.back() != 0);
  const int n = m.size() - 1;
  assert(f.size() == n);
  using std::swap;
  std::vector<T> fx = {1}, mx;
  while (true) {
    while (!f.empty() && f.back() == 0)
      f.pop_back();
    assert(!f.empty());
    if (f.size() == 1)
      break;
    if (f.size() < m.size())
      swap(f, m), swap(fx, mx);
    const int d = f.size() - m.size();
    const T c = f.back() / m.back();
    for (int i = 0; i < m.size(); i++)
      f[d + i] -= c * m[i];
    if (fx.size() < mx.size() + d)
      fx.resize(mx.size() + d);
    for (int i = 0; i < mx.size(); i++)
      fx[d + i] -= c * mx[i];
  }
  const T inv = 1 / f[0];
  for (T &c : fx)
    c *= inv;
  assert(fx.size() <= n);
  fx.resize(n);
  return fx;
}

} // namespace polynomial

} // namespace noshi91

#include <cassert>
#include <numeric>
#include <utility>
#include <vector>

namespace noshi91 {

namespace polynomial {

template <class T>
T bostan_mori(long long k, std::vector<T> num, std::vector<T> den) {
  assert(k >= 0);
  assert(num.size() + 1 == den.size());
  assert(den.front() != 0);
  if (num.empty())
    return 0;
  {
    const T h = 1 / den.front();
    for (T &c : num)
      c *= h;
    for (T &c : den)
      c *= h;
    den.erase(den.begin());
  }
  const int rank = 31 - __builtin_clz(num.size() * 2 - 1);
  const int n = 1 << rank;
  const T w = internal::info<T>.root[rank + 1];
  num.resize(n);
  internal::dft(num);
  den.resize(n);
  std::rotate(den.begin(), den.end() - 1, den.end());
  den.front() += 1;
  internal::dft(den);
  std::vector<T> num_, den_;
  const T inv2 = 1 / T(2);
  while (k) {
    den_ = den;
    internal::inv_dft(den);
    T r = 1;
    den[0] = 2 - den[0];
    for (int i = 0; i < n; i++)
      den[i] *= r, r *= w;
    internal::dft(den);
    den_.insert(den_.end(), den.begin(), den.end());
    for (int i = 0; i < n; i++)
      den[i] = den_[i * 2] * den_[i * 2 + 1];
    num_ = num;
    internal::inv_dft(num);
    r = 1;
    for (int i = 0; i < n; i++)
      num[i] *= r, r *= w;
    internal::dft(num);
    num_.insert(num_.end(), num.begin(), num.end());
    for (int i = 0; i < n; i++) {
      num_[i * 2] *= den_[i * 2 + 1];
      num_[i * 2 + 1] *= den_[i * 2];
    }
    if (k & 1) {
      r = inv2;
      for (int i = 0; i < n; i++) {
        num[i] = r * (num_[i * 2] - num_[i * 2 + 1]);
        r *= internal::info<T>.irate2[__builtin_ctz(~i)];
      }
    } else {
      for (int i = 0; i < n; i++)
        num[i] = inv2 * (num_[i * 2] + num_[i * 2 + 1]);
    }
    k >>= 1;
  }
  return std::accumulate(num.begin(), num.end(), T(0)) * ((1 - T::mod()) / n);
}

} // namespace polynomial

} // namespace noshi91

#include <iostream>

#include <atcoder/convolution>
#include <atcoder/modint>

using mint = atcoder::modint998244353;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int M, K, R;
  std::cin >> M >> K >> R;

  std::vector<mint> h(K + 1, -1 / mint(K));
  h[0] = 1;
  for (int i = 0; i <= K; i++)
    h[i] = -h[i] / mint(M);

  std::vector<mint> h_ = h; // (x-1)h(x)
  h_.insert(h_.begin(), 0);
  for (int i = 0; i <= K; i++)
    h_[i] -= h_[i + 1];

  std::vector<mint> rem;
  {
    rem = noshi91::polynomial::shifted_rev_inverse(h_, M);
    rem.erase(rem.begin());
    rem = atcoder::convolution(rem, h);
    rem.erase(rem.begin(), rem.begin() + K);
    rem.resize(K);
  }

  std::vector<mint> p = noshi91::polynomial::modular_inverse(rem, h);
  p.push_back(0), p[0] -= 1, p[1] += 1;

  const auto coef = [&](const int t) {
    return noshi91::polynomial::bostan_mori(t, p, h_);
  };

  std::cout << (coef(R) - coef(0)).val() << "\n";
  return 0;
}
0