結果

問題 No.3451 Same Numbers
コンテスト
ユーザー risujiroh
提出日時 2026-02-21 03:54:02
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 8,284 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,101 ms
コンパイル使用メモリ 360,412 KB
実行使用メモリ 12,576 KB
最終ジャッジ日時 2026-02-21 03:54:11
合計ジャッジ時間 8,552 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#if __INCLUDE_LEVEL__ == 0

#include __BASE_FILE__

using Mint = atcoder::modint998244353;

Comb<Mint> comb;

void Solve() {
  int N, M, E;
  IN(N, M, E);

  vector<Mint> toE(M + 1);
  for (int s : Rep1(1, M)) {
    toE[s] = Mint(s).pow(E);
  }

  // naive
  /* for (int K : Rep1(1, N)) {
    Mint P = comb.Inv(N - K + 1);
    Mint Q = 1 - P;

    Mint ans = 0;
    Mint pwP = 1;
    for (int s : Rep(0, DivCeil(M, K))) {
      Mint cur = 0;
      for (int i : Rep(0, M - K * s)) {
        cur += Q.pow(i) * comb.Homogeneous(s, i);
      }
      ans += (toE[s + 1] - toE[s]) * pwP * cur;
      pwP *= P;
    }
    OUT(ans);
  } */

  // int B = int(ceil(sqrt(M)));
  PARAM(int, B, 1200);

  // small K
  for (int K : Rep1(1, N)) {
    if (K == B) {
      break;
    }

    Mint P = comb.Inv(N - K + 1);
    Mint Q = 1 - P;

    Mint ans = 0;
    Mint pwP = 1;
    Mint pwQ = Q.pow(M);
    Mint cur = 1;
    for (int s : Rep(0, DivCeil(M, K))) {
      ans += (toE[s + 1] - toE[s]) * pwP * cur;
      pwP *= P;
      if (K * (s + 1) >= M) {
        break;
      }

      // O(M) for each K
      for (int i : Rev(Rep(M - K * (s + 1), M - K * s))) {
        if (K < N) {
          pwQ *= (N - K + 1) * comb.Inv(N - K);
        }
        cur -= pwQ * comb.Homogeneous(s, i);
      }

      cur -= pwQ * comb.Homogeneous(s + 1, M - K * (s + 1) - 1);
      cur *= N - K + 1;
    }
    OUT(ans);
  }

  // large K (small s)
  for (int K : Rep1(B, N)) {
    Mint P = comb.Inv(N - K + 1);
    Mint Q = 1 - P;

    Mint ans = 0;
    for (int s : Rep(0, DivCeil(M, K))) {
      int n = M - K * s;
      Mint cur = 1;
      Mint pwQ = Q.pow(n);
      for (int m : Rep(n, n + s)) {
        Mint sum = 0;
        for (int t : Rep1(0, s)) {
          if (m - t < n) {
            sum += (-(t & 1) | 1) * comb.Binom(s, t) * comb.Homogeneous(s, m - t);
          }
        }
        cur += pwQ * sum;
        pwQ *= Q;
      }
      ans += (toE[s + 1] - toE[s]) * cur;
    }
    OUT(ans);
  }
}

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

  Solve();
}

#elif __INCLUDE_LEVEL__ == 1

#include <bits/stdc++.h>

#include <atcoder/modint.hpp>

template <class T>
class Comb {
 public:
  Comb() = default;

  explicit Comb(int n) {
    Reserve(n);
  }

  void Reserve(int n) {
    const int sz = static_cast<int>(fact_.size());
    if (n < sz) {
      return;
    }
    fact_.resize(n + 1);
    const int nsz = static_cast<int>(fact_.capacity());
    fact_.resize(nsz);
    fact_inv_.resize(nsz);
    for (int i = sz; i < nsz; ++i) {
      fact_[i] = T(i) * fact_[i - 1];
    }
    fact_inv_.back() = T(1) / fact_.back();
    for (int i = nsz; --i > sz;) {
      fact_inv_[i - 1] = fact_inv_[i] * T(i);
    }
  }

  T Fact(int n) {
    assert(n >= 0);
    Reserve(n);
    return fact_[n];
  }

  T FactInv(int n) {
    if (n < 0) {
      return T(0);
    }
    Reserve(n);
    return fact_inv_[n];
  }

  T FactRatio(int a, int b) {
    if (a >= 0) {
      return Fact(a) * FactInv(b);
    }
    assert(b < 0);
    const T t = FactRatio(~b, ~a);
    return (a - b) % 2 == 0 ? t : -t;
  }

  T Inv(int n) {
    assert(n != 0);
    return FactRatio(n - 1, n);
  }

  T Prod(std::ranges::iota_view<int, int> r) {
    return FactRatio(r.end()[-1], r[-1]);
  }

  T ProdInv(std::ranges::iota_view<int, int> r) {
    assert(r[0] > 0 || r.end()[-1] < 0);
    return FactRatio(r[-1], r.end()[-1]);
  }

  T Perm(int n, int k) {
    assert(n >= 0 ? true : k > n);
    return FactRatio(n, n - k);
  }

  T PermInv(int n, int k) {
    assert(n >= 0 ? k <= n : true);
    return FactRatio(n - k, n);
  }

  T Binom(int n, int k) {
    k = std::max(k, n - k);
    return Perm(n, k) * FactInv(k);
  }

  T BinomInv(int n, int k) {
    assert(n >= 0 ? 0 <= k && k <= n : 0 <= k || k <= n);
    k = std::max(k, n - k);
    return PermInv(n, k) * Fact(k);
  }

  T Multinom(std::span<const int> ks) {
    if (ks.size() < 2) {
      return T(1);
    }
    const int n = std::reduce(ks.begin(), ks.end());
    const int& min_k = *std::ranges::min_element(ks);
    T ret = FactRatio(n, min_k);
    for (const int& k : ks) {
      if (&k != &min_k) {
        ret *= FactInv(k);
      }
    }
    return ret;
  }

  template <class... Ks>
  requires(...&& std::same_as<Ks, int>)
      T Multinom(Ks... ks) {
    return Multinom(std::initializer_list<int>{ks...});
  }

  T MultinomInv(std::span<const int> ks) {
    if (ks.size() < 2) {
      return T(1);
    }
    const int n = std::reduce(ks.begin(), ks.end());
    const int& min_k = *std::ranges::min_element(ks);
    assert(n >= 0 ? min_k >= 0
                  : std::ranges::all_of(ks, [&](auto& k) { return &k == &min_k || k >= 0; }));
    T ret = FactRatio(min_k, n);
    for (const int& k : ks) {
      if (&k != &min_k) {
        ret *= Fact(k);
      }
    }
    return ret;
  }

  template <class... Ks>
  requires(...&& std::same_as<Ks, int>)
      T MultinomInv(Ks... ks) {
    return MultinomInv(std::initializer_list<int>{ks...});
  }

  T Homogeneous(int n, int k) {
    return Binom(n + k - 1, k);
  }

  T Catalan(int n) {
    assert(n >= 0);
    return Fact(2 * n) * FactInv(n) * FactInv(n + 1);
  }

  T Catalan(int n, int k) {
    assert(0 <= k && k <= n);
    return T(n - k + 1) * Fact(n + k) * FactInv(n + 1) * FactInv(k);
  }

 private:
  std::vector<T> fact_{T(1)};
  std::vector<T> fact_inv_{T(1)};
};

template <class T>
concept MyRange =
    std::ranges::range<T> &&
    !std::convertible_to<T, std::string_view> &&
    !std::convertible_to<T, std::filesystem::path>;

template <class T>
concept MyTuple = std::__is_tuple_like<T>::value && !MyRange<T>;

namespace std {

istream& operator>>(istream& is, MyRange auto&& r) {
  for (auto&& e : r) {
    is >> e;
  }
  return is;
}

istream& operator>>(istream& is, MyTuple auto&& t) {
  apply([&](auto&... xs) { (is >> ... >> xs); }, t);
  return is;
}

ostream& operator<<(ostream& os, MyRange auto&& r) {
  auto sep = "";
  for (auto&& e : r) {
    os << exchange(sep, " ") << forward<decltype(e)>(e);
  }
  return os;
}

ostream& operator<<(ostream& os, MyTuple auto&& t) {
  auto sep = "";
  apply([&](auto&... xs) { ((os << exchange(sep, " ") << xs), ...); }, t);
  return os;
}

template <class T, atcoder::internal::is_modint_t<T>* = nullptr>
istream& operator>>(istream& is, T& x) {
  int v;
  is >> v;
  x = T::raw(v);
  return is;
}

template <class T, atcoder::internal::is_modint_t<T>* = nullptr>
ostream& operator<<(ostream& os, const T& x) {
  return os << x.val();
}

}  // namespace std

template <class T>
class OneBased {
 public:
  explicit OneBased(T&& x) : ref_(std::forward<T>(x)) {}

  template <class... Ts>
  requires(sizeof...(Ts) > 1)
      OneBased(Ts&&... xs) : ref_(std::forward_as_tuple(std::forward<Ts>(xs)...)) {}

  friend std::istream& operator>>(std::istream& is, OneBased x) {
    if constexpr (MyRange<T>) {
      for (auto&& e : x.ref_) {
        is >> ::OneBased(e);
      }
    } else if constexpr (MyTuple<T>) {
      std::apply([&](auto&... xs) { (is >> ... >> ::OneBased(xs)); }, x.ref_);
    } else {
      is >> x.ref_;
      --x.ref_;
    }
    return is;
  }

  friend std::ostream& operator<<(std::ostream& os, OneBased x) {
    if constexpr (MyRange<T>) {
      auto f = [](auto&& e) { return ::OneBased(std::forward<decltype(e)>(e)); };
      os << (x.ref_ | std::views::transform(f));
    } else if constexpr (MyTuple<T>) {
      std::apply([&](auto&... xs) { os << std::tuple(::OneBased(xs)...); }, x.ref_);
    } else {
      os << ++x.ref_;
      --x.ref_;
    }
    return os;
  }

 private:
  T ref_;
};

template <class T>
OneBased(T&&) -> OneBased<T>;

template <class... Ts>
OneBased(Ts&&...) -> OneBased<std::tuple<Ts...>>;

using namespace std;

#define LAMBDA2(x, y, ...) ([&](auto&& x, auto&& y) -> decltype(auto) { return __VA_ARGS__; })
#define Rev views::reverse
#define Rep(...) [](int l, int r) { return views::iota(min(l, r), r); }(__VA_ARGS__)
#define Rep1(...) [](int l, int r) { return Rep(l, r + 1); }(__VA_ARGS__)
#define DivCeil(...) LAMBDA2(x, y, x / y + ((x ^ y) >= 0 && x % y))(__VA_ARGS__)
#define PARAM(T, NAME, val) constexpr T NAME = val
#define IN(...) (cin >> forward_as_tuple(__VA_ARGS__))
#define OUT(...) (cout << forward_as_tuple(__VA_ARGS__) << '\n')

#endif  // __INCLUDE_LEVEL__ == 1
0