#594892 (C++17) No.1321 塗るめた

提出ソース

結果

問題	No.1321 塗るめた
ユーザー	りあん
提出日時	2020-12-18 10:20:20
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	889 ms / 2,000 ms
コード長	12,545 bytes
コンパイル時間	3,247 ms
コンパイル使用メモリ	228,612 KB
実行使用メモリ	45,408 KB
最終ジャッジ日時	2023-10-21 07:57:00
合計ジャッジ時間	13,073 ms
ジャッジサーバーID （参考情報）	judge10 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	21 ms 17,392 KB
testcase_01	AC	24 ms 21,464 KB
testcase_02	AC	20 ms 17,392 KB
testcase_03	AC	20 ms 17,392 KB
testcase_04	AC	20 ms 17,392 KB
testcase_05	AC	20 ms 17,392 KB
testcase_06	AC	21 ms 17,392 KB
testcase_07	AC	20 ms 17,392 KB
testcase_08	AC	22 ms 21,140 KB
testcase_09	AC	22 ms 21,140 KB
testcase_10	AC	20 ms 17,392 KB
testcase_11	AC	22 ms 21,140 KB
testcase_12	AC	213 ms 27,456 KB
testcase_13	AC	635 ms 38,448 KB
testcase_14	AC	119 ms 24,700 KB
testcase_15	AC	74 ms 24,320 KB
testcase_16	AC	107 ms 25,624 KB
testcase_17	AC	27 ms 21,404 KB
testcase_18	AC	109 ms 30,504 KB
testcase_19	AC	42 ms 22,704 KB
testcase_20	AC	74 ms 23,972 KB
testcase_21	AC	293 ms 30,024 KB
testcase_22	AC	185 ms 32,252 KB
testcase_23	AC	152 ms 31,732 KB
testcase_24	AC	231 ms 33,196 KB
testcase_25	AC	111 ms 30,660 KB
testcase_26	AC	125 ms 31,016 KB
testcase_27	AC	325 ms 35,192 KB
testcase_28	AC	329 ms 35,312 KB
testcase_29	AC	305 ms 34,692 KB
testcase_30	AC	108 ms 30,524 KB
testcase_31	AC	494 ms 34,936 KB
testcase_32	AC	241 ms 28,048 KB
testcase_33	AC	78 ms 23,820 KB
testcase_34	AC	42 ms 24,248 KB
testcase_35	AC	38 ms 23,500 KB
testcase_36	AC	889 ms 45,408 KB
testcase_37	AC	465 ms 33,740 KB
testcase_38	AC	463 ms 33,740 KB
testcase_39	AC	461 ms 33,740 KB
testcase_40	AC	463 ms 33,728 KB
testcase_41	AC	462 ms 33,732 KB
testcase_42	AC	21 ms 17,392 KB
testcase_43	AC	241 ms 28,048 KB
testcase_44	AC	78 ms 23,820 KB
testcase_45	AC	42 ms 24,248 KB
testcase_46	AC	27 ms 21,932 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// from: https://judge.yosupo.jp/submission/856

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

template<unsigned P> struct ModInt {
  using M = ModInt;
  unsigned v;
  constexpr ModInt() : v(0) {}
  constexpr ModInt(unsigned _v, int) : v(_v) {}
  template<class Z> ModInt(const Z& a) : v((a < 0 ? P - -a % P : a) % P) {}
  static constexpr unsigned p() { return P; }
  M operator+() const { return *this; }
  M operator-() const { return {v ? P - v : 0, 0}; }
  explicit operator bool() const noexcept { return v; }
  bool operator!() const noexcept { return !(bool)*this; }
  M& operator*=(M r) { v = (uint64_t)v * r.v % P; return *this; }
  M& operator/=(M r) { return *this *= r.inv(); }
  M& operator+=(M r) { if ((v += r.v) >= P) v -= P; return *this; }
  M& operator-=(M r) { if ((v += P - r.v) >= P) v -= P; return *this; }
  friend M operator*(M l, M r) { return M(l) *= r; }
  friend M operator/(M l, M r) { return M(l) /= r; }
  friend M operator+(M l, M r) { return M(l) += r; }
  friend M operator-(M l, M r) { return M(l) -= r; }
  friend ostream& operator<<(ostream& os, M r) { return os << r.v; }
  friend bool operator==(M l, M r) { return l.v == r.v; }
  friend bool operator!=(M l, M r) { return !(l == r); }
  M inv() const {
    int a = v, b = P, x = 1, u = 0;
    while (b) {
      int q = a / b;
      swap(a -= q * b, b);
      swap(x -= q * u, u);
    }
    assert(a == 1);
    return x;
  }
  template<class Z> M pow(Z n) const {
    if (n < 0) return pow(-n).inv();
    M res = 1;
    for (M a = *this; n; a *= a, n >>= 1) if (n & 1) res *= a;
    return res;
  }
};
using Mint = ModInt<998244353>;
constexpr int N = 1 << 20;
struct Fact {
  V<Mint> v;
  Fact(int n) : v(n + 1, 1) {
    for (int i = 1; i <= n; ++i) v[i] = i * v[i - 1];
  }
  Mint operator[](int i) const { return v[i]; }
} fact(N);
struct Finv {
  V<Mint> v;
  Finv(int n) : v(n + 1, 1 / fact[n]) {
    for (int i = n; i; --i) v[i - 1] = i * v[i];
  }
  Mint operator[](int i) const { return v[i]; }
} finv(N);
struct Minv {
  V<Mint> v;
  Minv(int n) : v(n) {
    for (int i = 1; i <= n; ++i) v[i - 1] = fact[i - 1] * finv[i];
  }
  Mint operator[](int i) const { return v[i - 1]; }
} minv(N);
Mint comb(int n, int r) {
  if (r < 0 or r > n) return 0;
  return fact[n] * finv[r] * finv[n - r];
}

namespace NTT {
  constexpr int LG = 20;
  constexpr unsigned P = Mint::p();
  const Mint g = [] { for (Mint a = 3; ; ++a.v) if (a.pow((P - 1) / 2) != 1) return a; }();
  void ntt(const V<Mint>& a, Mint A[], int n) {
    int lg = __lg(n);
    assert(n == 1 << lg);
    assert(lg <= LG);
    assert((P - 1) % n == 0);
    static VV<Mint> w(1, V<Mint>(1, 1));
    for (int k = 1; k <= lg; ++k) if (k >= (int)w.size()) {
      w.emplace_back(1 << (k - 1));
      auto z = g.pow((P - 1) >> k);
      for (int i = 0; i < 1 << (k - 1); ++i) {
        w[k][i] = w[k - 1][i >> 1];
        if (i & 1) w[k][i] *= z;
      }
    }
    for (int i = 0, j = n / 2; j < n; ++i, ++j) {
      auto ai = i < (int)a.size() ? a[i] : 0;
      auto aj = j < (int)a.size() ? a[j] : 0;
      uint64_t x = P + ai.v - aj.v;
      A[i] = ai + aj;
      A[j].v = w[lg][i].v * x % P;
    }
    for (int k = lg - 1; k; --k) {
      int d = 1 << (k - 1);
      for (int s = 0; s < n; s += 2 * d) {
        for (int i = s, j = s + d, p = i - s; i < s + d; ++i, ++j) {
          uint64_t x = P + A[i].v - A[j].v;
          A[i] = A[i] + A[j];
          A[j].v = w[k][p++].v * x % P;
        }
      }
    }
  }
  void intt(Mint A[], int n) {
    int lg = __lg(n);
    assert(n == 1 << lg);
    assert(lg <= LG);
    assert((P - 1) % n == 0);
    static Mint w[1 << (LG - 1)];
    if (!w[0]) {
      w[0] = 1;
      for (int k = 1; k < LG; ++k) {
        int d = 1 << (k - 1);
        auto z = g.inv().pow((P - 1) >> (k + 1));
        for (int i = 0; i < d; ++i) {
          w[i + d] = w[i] * z;
        }
      }
    }
    for (int k = 1; k <= lg; ++k) {
      int d = 1 << (k - 1);
      for (int s = 0, p = 0; s < n; s += 2 * d) {
        uint64_t nw = w[p++].v;
        for (int i = s, j = s + d; i < s + d; ++i, ++j) {
          uint64_t x = P + A[i].v - A[j].v;
          A[i] = A[i] + A[j];
          A[j].v = nw * x % P;
        }
      }
    }
  }
  Mint A[1 << LG], B[1 << LG];
  V<Mint> multiply(const V<Mint>& a, const V<Mint>& b) {
    int na = a.size(), nb = b.size();
    if (!na or !nb) return {};
    int nc = na + nb - 1, n = 1 << __lg(2 * nc - 1);
    if (min(na, nb) < 16) {
      V<Mint> c(nc);
      for (int i = 0; i < na; ++i) for (int j = 0; j < nb; ++j) {
        c[i + j] += a[i] * b[j];
      }
      return c;
    }
    ntt(a, A, n);
    ntt(b, B, n);
    for (int i = 0; i < n; ++i) A[i] *= B[i];
    intt(A, n);
    V<Mint> c(nc);
    for (int i = 0; i < nc; ++i) c[i] = A[i] * minv[n];
    return c;
  }
}

template<class T, V<T> Mul(const V<T>&, const V<T>&)>
struct FormalPowerSeries : public V<T> {
  using F = FormalPowerSeries;
  using V<T>::V;
  FormalPowerSeries() {}
  FormalPowerSeries(const V<T>& v) : V<T>(v) {}
  T get(int i) const { return i < (int)this->size() ? (*this)[i] : 0; }
  F cut(int n) const { return F(begin(*this), begin(*this) + min<int>(n, this->size())); }
  F trim() {
    while (not this->empty() and !this->back()) this->pop_back();
    return *this;
  }
  F operator+() const { return *this; }
  F operator-() const { F res = *this; for (auto&& e : res) e = -e; return res; }
  explicit operator bool() const noexcept { return not F(*this).trim().empty(); }
  bool operator!() const noexcept { return !(bool)*this; }
  F& operator*=(const F& r) { return *this = Mul(*this, r); }
  F& operator*=(const T& r) { for (auto&& e : *this) e *= r; return *this; }
  F& operator/=(const F& r) {
    int n = max(this->size(), r.size());
    *this *= r.inv(n);
    this->resize(n);
    return *this;
  }
  F& operator/=(const T& r) { return *this *= 1 / r; }
  F& operator+=(const F& r) {
    this->resize(max(this->size(), r.size()));
    for (int i = 0; i < (int)r.size(); ++i) (*this)[i] += r[i];
    return *this;
  }
  F& operator+=(const T& r) { return *this += F(1, r); }
  F& operator-=(const F& r) {
    this->resize(max(this->size(), r.size()));
    for (int i = 0; i < (int)r.size(); ++i) (*this)[i] -= r[i];
    return *this;
  }
  F& operator-=(const T& r) { return *this -= F(1, r); }
  F& operator<<=(int n) {
    if (n < 0) return *this >>= -n;
    this->insert(begin(*this), n, 0);
    return *this;
  }
  F& operator>>=(int n) {
    if (n < 0) return *this <<= -n;
    this->erase(begin(*this), begin(*this) + n);
    return *this;
  }
  friend F operator*(const F& l, const F& r) { return F(l) *= r; }
  friend F operator*(const F& l, const T& r) { return F(l) *= r; }
  friend F operator*(const T& l, const F& r) { return r * l; }
  friend F operator/(const F& l, const F& r) { return F(l) /= r; }
  friend F operator/(const F& l, const T& r) { return F(l) /= r; }
  friend F operator/(const T& l, const F& r) { return r.inv() * l; }
  friend F operator+(const F& l, const F& r) { return F(l) += r; }
  friend F operator+(const F& l, const T& r) { return F(l) += r; }
  friend F operator+(const T& l, const F& r) { return r + l; }
  friend F operator-(const F& l, const F& r) { return F(l) -= r; }
  friend F operator-(const F& l, const T& r) { return F(l) -= r; }
  friend F operator-(const T& l, const F& r) { return -r + l; }
  friend ostream& operator<<(ostream& os, const F& r) {
    int n = F(r).trim().size();
    if (!n) return os << '0';
    for (int i = 0; i < n; ++i) if (r[i]) {
      if (!i or r[i] != 1) os << r[i];
      if (i) cout << 'X';
      if (i >= 2) cout << '^' << i;
      if (i < n - 1) cout << " + ";
    }
    return os;
  }
  friend F operator<<(const F& l, int n) { return F(l) <<= n; }
  friend F operator>>(const F& l, int n) { return F(l) >>= n; }
  friend bool operator==(const F& l, const F& r) { return (l - r).trim().empty(); }
  friend bool operator==(const F& l, const T& r) { return l == F(1, r); }
  friend bool operator==(const T& l, const F& r) { return F(1, l) == r; }
  friend bool operator!=(const F& l, const F& r) { return !(l == r); }
  friend bool operator!=(const F& l, const T& r) { return !(l == r); }
  friend bool operator!=(const T& l, const F& r) { return !(l == r); }
  F inv(int n = -1) const {
    assert(get(0));
    if (n == -1) n = this->size();
    F g{1 / (*this)[0]};
    for (int m = 1; m < n; m *= 2) {
      g = (2 * g - cut(2 * m) * g * g).cut(2 * m);
    }
    return g.cut(n);
  }
  F diff() const {
    int n = this->size();
    F res(n - 1);
    for (int i = 1; i < n; ++i) res[i - 1] = i * (*this)[i];
    return res;
  }
  F integ() const {
    int n = this->size();
    F res(n + 1);
    for (int i = 1; i <= n; ++i) res[i] = (*this)[i - 1] / i;
    return res;
  }
  F log(int n = -1) const {
    assert(get(0) == 1);
    if (n == -1) n = this->size();
    return (diff() * inv(n - 1)).cut(n - 1).integ();
  }
  F exp(int n = -1) const {
    assert(!get(0));
    if (n == -1) n = this->size();
    F g{1};
    for (int m = 1; m < n; m *= 2) {
      g = (g * (1 + cut(2 * m) - g.log(2 * m))).cut(2 * m);
    }
    return g.cut(n);
  }
  F sqrt(int n = -1) const {
    assert(get(0) == 1);
    if (n == -1) n = this->size();
    F g{1};
    for (int m = 1; m < n; m *= 2) {
      g = ((g + cut(2 * m) * g.inv(2 * m)) / 2).cut(2 * m);
    }
    return g.cut(n);
  }
};
template<class T> V<T> naive_multiply(const V<T>& a, const V<T>& b) {
  int n = a.size(), m = b.size();
  V<T> c(n + m - 1);
  for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
    c[i + j] += a[i] * b[j];
  }
  return c;
}
// using FPS = FormalPowerSeries<double, naive_multiply>; // for debug

using FPS = FormalPowerSeries<Mint, NTT::multiply>;
template<> FPS FPS::inv(int n) const {
  using namespace NTT;
  assert(get(0));
  if (n == -1) n = this->size();
  if (min<int>(this->size(), n) < 16) {
    FPS g(n);
    g[0] = 1 / (*this)[0];
    for (int i = 1; i < n; ++i) {
      for (int j = 1; j < min<int>(this->size(), i + 1); ++j) {
        g[i] -= (*this)[j] * g[i - j];
      }
      g[i] *= g[0];
    }
    return g;
  }
  F g{1 / (*this)[0]};
  for (int m = 1; m < n; m *= 2) {
    ntt(cut(2 * m), A, 4 * m);
    ntt(g, B, 4 * m);
    for (int i = 0; i < 4 * m; ++i) {
      A[i] *= B[i] * B[i];
    }
    intt(A, 4 * m);
    g.resize(2 * m);
    for (int i = 0; i < 2 * m; ++i) {
      g[i] = 2 * g[i] - A[i] * minv[4 * m];
    }
  }
  return g.cut(n);
}
template<> FPS& FPS::operator/=(const FPS& r) {
  int n = max(this->size(), r.size());
  if (r.size() < 16) {
    this->resize(n);
    auto ir0 = 1 / r[0];
    for (int i = 0; i < n; ++i) {
      for (int j = 1; j < min<int>(r.size(), i + 1); ++j) {
        (*this)[i] -= r[j] * (*this)[i - j];
      }
      (*this)[i] *= ir0;
    }
    return *this;
  }
  *this *= r.inv(n);
  this->resize(n);
  return *this;
}
template<> FPS FPS::integ() const {
  int n = this->size();
  F res(n + 1);
  for (int i = 1; i <= n; ++i) res[i] = (*this)[i - 1] * minv[i];
  return res;
}

pair<FPS, FPS> polynomial_divmod(FPS a, FPS b) {
  a.trim(), b.trim();
  assert(b);
  if (a.size() < b.size()) return {{}, a};
  reverse(begin(a), end(a));
  reverse(begin(b), end(b));
  int m = a.size() - b.size() + 1;
  auto q = (a.cut(m) * b.inv(m)).cut(m);
  reverse(begin(a), end(a));
  reverse(begin(b), end(b));
  reverse(begin(q), end(q));
  return {q, a - q * b};
}
template<class T> V<T> multipoint_evaluation(const FPS& f, const V<T>& p) {
  int n = p.size();
  V<FPS> t(2 * n);
  for (int i = 0; i < n; ++i) {
    t[n + i] = FPS{-p[i], 1};
  }
  for (int i = n - 1; i; --i) {
    t[i] = t[2 * i] * t[2 * i + 1];
  }
  t[1] = polynomial_divmod(f, t[1]).second;
  for (int i = 1; i < n; ++i) {
    t[2 * i] = polynomial_divmod(t[i], t[2 * i]).second;
    t[2 * i + 1] = polynomial_divmod(t[i], t[2 * i + 1]).second;
  }
  V<T> res(n);
  for (int i = 0; i < n; ++i) {
    res[i] = t[n + i].get(0);
  }
  return res;
}

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n, m, k;
  cin >> n >> m >> k;
  FPS f(n + 1);
  for (int i = k; i <= n; ++i) {
    f[i] = comb(n, i) * Mint(m).pow(n - i);
  }
  V<Mint> p(k + 1);
  for (int i = 0; i < k + 1; ++i) {
    p[i] = Mint(i);
  }
  auto res = multipoint_evaluation(f, p);
  Mint ans(0);
  for (int i = 1; i < k + 1; ++i) {
    ans += res[i] * comb(k, i) * Mint(-1).pow(k - i);
  }
  cout << ans * comb(m, k) << '\n';
  return 0;
}

yukicoder

結果

テストケース

ソースコード