#879295 (C++17) No.2345 max(l,r)

提出ソース

結果

問題	No.2345 max(l,r)
ユーザー	KoD
提出日時	2023-06-09 22:38:57
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	71 ms / 2,000 ms
コード長	10,621 bytes
コンパイル時間	1,765 ms
コンパイル使用メモリ	143,792 KB
実行使用メモリ	7,784 KB
最終ジャッジ日時	2024-06-10 13:46:29
合計ジャッジ時間	4,765 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	18 ms 6,944 KB
testcase_02	AC	14 ms 6,940 KB
testcase_03	AC	14 ms 6,940 KB
testcase_04	AC	15 ms 6,940 KB
testcase_05	AC	14 ms 6,940 KB
testcase_06	AC	15 ms 6,940 KB
testcase_07	AC	14 ms 6,940 KB
testcase_08	AC	15 ms 6,940 KB
testcase_09	AC	15 ms 6,944 KB
testcase_10	AC	14 ms 6,940 KB
testcase_11	AC	14 ms 6,940 KB
testcase_12	AC	14 ms 6,944 KB
testcase_13	AC	14 ms 6,940 KB
testcase_14	AC	15 ms 6,944 KB
testcase_15	AC	14 ms 6,944 KB
testcase_16	AC	15 ms 6,944 KB
testcase_17	AC	14 ms 6,940 KB
testcase_18	AC	14 ms 6,940 KB
testcase_19	AC	13 ms 6,940 KB
testcase_20	AC	14 ms 6,940 KB
testcase_21	AC	15 ms 6,944 KB
testcase_22	AC	14 ms 6,940 KB
testcase_23	AC	15 ms 6,940 KB
testcase_24	AC	5 ms 6,940 KB
testcase_25	AC	9 ms 6,940 KB
testcase_26	AC	8 ms 6,940 KB
testcase_27	AC	10 ms 6,944 KB
testcase_28	AC	10 ms 6,944 KB
testcase_29	AC	15 ms 6,940 KB
testcase_30	AC	11 ms 6,940 KB
testcase_31	AC	19 ms 6,940 KB
testcase_32	AC	10 ms 6,944 KB
testcase_33	AC	10 ms 6,944 KB
testcase_34	AC	7 ms 6,944 KB
testcase_35	AC	9 ms 6,944 KB
testcase_36	AC	9 ms 6,944 KB
testcase_37	AC	10 ms 6,944 KB
testcase_38	AC	26 ms 7,784 KB
testcase_39	AC	22 ms 6,940 KB
testcase_40	AC	24 ms 6,944 KB
testcase_41	AC	25 ms 7,648 KB
testcase_42	AC	20 ms 6,940 KB
testcase_43	AC	20 ms 6,944 KB
testcase_44	AC	23 ms 6,944 KB
testcase_45	AC	26 ms 7,396 KB
testcase_46	AC	21 ms 6,944 KB
testcase_47	AC	25 ms 7,524 KB
testcase_48	AC	15 ms 6,940 KB
testcase_49	AC	15 ms 6,940 KB
testcase_50	AC	15 ms 6,940 KB
testcase_51	AC	16 ms 6,940 KB
testcase_52	AC	15 ms 6,940 KB
testcase_53	AC	13 ms 6,940 KB
testcase_54	AC	14 ms 6,944 KB
testcase_55	AC	14 ms 6,940 KB
testcase_56	AC	16 ms 6,940 KB
testcase_57	AC	15 ms 6,940 KB
testcase_58	AC	22 ms 6,940 KB
testcase_59	AC	22 ms 6,940 KB
testcase_60	AC	22 ms 6,944 KB
testcase_61	AC	23 ms 6,940 KB
testcase_62	AC	22 ms 6,944 KB
testcase_63	AC	22 ms 6,940 KB
testcase_64	AC	23 ms 6,944 KB
testcase_65	AC	22 ms 6,940 KB
testcase_66	AC	23 ms 6,940 KB
testcase_67	AC	23 ms 6,940 KB
testcase_68	AC	71 ms 6,944 KB

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

ソースコード

raw source code

#define MULTEST

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>

namespace kod {
namespace util {

template <class F> class fixed_point : private F {
  constexpr fixed_point(F&& f) noexcept : F(std::forward<F>(f)) {}
  template <class G> friend constexpr decltype(auto) make_fixed(G&&) noexcept;

 public:
  template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const noexcept {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <class G> [[nodiscard]] constexpr decltype(auto) make_fixed(G&& g) noexcept {
  using F = std::decay_t<G>;
  return fixed_point<F>(std::forward<F>(g));
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace util {

class forward_loop {
  int x, y;
  constexpr forward_loop(int x, int y) noexcept : x(x), y(y) {}
  friend constexpr forward_loop rep(int, int) noexcept;
  friend constexpr forward_loop rep(int) noexcept;

 public:
  constexpr forward_loop begin() const noexcept { return *this; }
  constexpr std::monostate end() const noexcept { return {}; }
  constexpr bool operator!=(std::monostate) const noexcept { return x < y; }
  constexpr void operator++() const noexcept {}
  constexpr int operator*() noexcept { return x++; }
};

[[nodiscard]] constexpr forward_loop rep(int l, int r) noexcept { return forward_loop(l, r); }
[[nodiscard]] constexpr forward_loop rep(int n) noexcept { return forward_loop(0, n); }

class backward_loop {
  int x, y;
  constexpr backward_loop(int x, int y) noexcept : x(x), y(y) {}
  friend constexpr backward_loop revrep(int, int) noexcept;
  friend constexpr backward_loop revrep(int) noexcept;

 public:
  constexpr backward_loop begin() const noexcept { return *this; }
  constexpr std::monostate end() const noexcept { return {}; }
  constexpr bool operator!=(std::monostate) const noexcept { return x > y; }
  constexpr void operator++() const noexcept {}
  constexpr int operator*() noexcept { return --x; }
};

[[nodiscard]] constexpr backward_loop revrep(int l, int r) noexcept { return backward_loop(r, l); }
[[nodiscard]] constexpr backward_loop revrep(int n) noexcept { return backward_loop(n, 0); }

template <class F> constexpr void repeat(int n, const F& f) noexcept {
  assert(n >= 0);
  while (n--) f();
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace util {

namespace stdio_impl {

template <class T> T scan() {
  T x;
  std::cin >> x;
  return x;
}
struct scan_any {
  template <class T> operator T() const { return scan<T>(); }
};

}  // namespace stdio_impl

template <class T = void> decltype(auto) scan() {
  if constexpr (std::is_same_v<T, void>) return stdio_impl::scan_any{};
  else return stdio_impl::scan<T>();
}
template <class T, std::size_t N> std::array<T, N> scan_arr() {
  std::array<T, N> a;
  for (auto& x : a) x = scan<T>();
  return a;
}
template <class T> std::vector<T> scan_vec(int n) {
  if (n == -1) n = scan<int>();
  assert(n >= 0);
  std::vector<T> v;
  v.reserve(n);
  while (n--) v.push_back(scan<T>());
  return v;
}

void flush() { std::cout << std::flush; }
void print() {}
template <class T, class... Args> void print(const T& x, const Args&... args) {
  std::cout << x;
  if (sizeof...(args) != 0) std::cout << ' ';
  print(args...);
}
template <class... Args> void println(const Args&... args) {
  print(args...);
  std::cout << '\n';
}
template <class C> void print_seq(const C& c, const char* sep = " ", const char* end = "\n") {
  bool f = false;
  for (const auto& x : c) {
    if (f) std::cout << sep;
    else f = true;
    std::cout << x;
  }
  std::cout << end;
}

}  // namespace util
}  // namespace kod

namespace kod {
namespace sol {

using ll = long long;
using uint = unsigned;
using ull = unsigned long long;

using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;

using namespace util;

constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr ll infll = std::numeric_limits<ll>::max() / 2;

constexpr ll floor_div(ll x, ll y) noexcept {
  assert(y != 0);
  return x / y - ((x ^ y) < 0 && x % y != 0);
}
constexpr ll ceil_div(ll x, ll y) noexcept {
  assert(y != 0);
  return x / y + ((x ^ y) >= 0 && x % y != 0);
}

template <class T> constexpr bool setmin(T& lhs, const T& rhs) noexcept {
  if (lhs > rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}
template <class T> constexpr bool setmax(T& lhs, const T& rhs) noexcept {
  if (lhs < rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

void run();

}  // namespace sol
}  // namespace kod

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout << std::fixed << std::setprecision(20);
  int cases = 1;
#ifdef MULTEST
  std::cin >> cases;
#endif
  while (cases--) kod::sol::run();
  return 0;
}

#ifdef KOD_LOCAL
#define OJ_LOCAL(a, b) b
#include <kodlib/misc/debug>
#else
#define OJ_LOCAL(a, b) a
#define DBG(...)
#define SHOW(...)
#endif

namespace kod {
namespace mod {

namespace finite_field_impl {

constexpr bool is_valid_mod(unsigned m) noexcept {
  if (m <= 1 || (1u << 31) <= m) return false;
  for (unsigned i = 2; i * i <= m; ++i) {
    if (m % i == 0) return false;
  }
  return true;
}

constexpr long long rem_euclid(long long x, long long y) noexcept {
  if (x >= 0) return x < y ? x : x % y;
  if (x >= -y) return x + y;
  return (x %= y) == 0 ? 0 : x + y;
}

template <unsigned MOD, std::enable_if_t<is_valid_mod(MOD)>* = nullptr> class finite_field {
 public:
  constexpr finite_field() noexcept : v(0) {}
  constexpr finite_field(long long x) noexcept : v(rem_euclid(x, MOD)) {}

  constexpr finite_field& operator+=(const finite_field& x) noexcept {
    v += x.v;
    if (v >= MOD) v -= MOD;
    return *this;
  }
  constexpr finite_field& operator-=(const finite_field& x) noexcept {
    if (v < x.v) v += MOD;
    v -= x.v;
    return *this;
  }
  constexpr finite_field& operator*=(const finite_field& x) noexcept {
    v = (unsigned long long)v * x.v % MOD;
    return *this;
  }
  constexpr finite_field& operator/=(const finite_field& x) noexcept { return *this *= x.inv(); }

  constexpr finite_field operator+() const noexcept { return *this; }
  constexpr finite_field operator-() const noexcept { return raw(v == 0 ? 0 : MOD - v); }
  friend constexpr finite_field operator+(finite_field x, const finite_field& y) noexcept { return x += y; }
  friend constexpr finite_field operator-(finite_field x, const finite_field& y) noexcept { return x -= y; }
  friend constexpr finite_field operator*(finite_field x, const finite_field& y) noexcept { return x *= y; }
  friend constexpr finite_field operator/(finite_field x, const finite_field& y) noexcept { return x /= y; }
  friend constexpr bool operator==(const finite_field& x, const finite_field& y) noexcept { return x.v == y.v; }
  friend constexpr bool operator!=(const finite_field& x, const finite_field& y) noexcept { return x.v != y.v; }
  friend std::ostream& operator<<(std::ostream& s, const finite_field& x) noexcept { return s << x.v; }

  constexpr unsigned val() const noexcept { return v; }
  constexpr finite_field inv() const noexcept { return pow(MOD - 2); }
  constexpr finite_field pow(long long e) const noexcept {
    if (v == 0) {
      assert(e >= 0);
      return raw(e == 0);
    }
    unsigned long long x = 1, y = v;
    for (e = rem_euclid(e, MOD - 1); e > 0; e >>= 1) {
      if (e & 1) x = x * y % MOD;
      y = y * y % MOD;
    }
    return raw(x);
  }

  static constexpr unsigned mod() noexcept { return MOD; }
  static constexpr finite_field raw(unsigned x) noexcept {
    finite_field ret;
    ret.v = x;
    return ret;
  }

  static finite_field fact(int n) noexcept {
    assert(n >= 0);
    static std::vector v = {raw(1)};
    for (int i = (int)v.size(); i <= n; ++i) v.push_back(v.back() * finite_field(i));
    return v[n];
  }
  static finite_field inv(int n) noexcept {
    assert(n >= 1);
    static std::vector v = {raw(0), raw(1)};
    for (int i = (int)v.size(); i <= n; ++i) v.push_back(-raw(mod() / i) * v[mod() % i]);
    return v[n];
  }
  static finite_field ifact(int n) noexcept {
    assert(n >= 0);
    static std::vector v = {raw(1)};
    for (int i = (int)v.size(); i <= n; ++i) v.push_back(v.back() * inv(i));
    return v[n];
  }
  static finite_field factpow(int n, int d) noexcept { return 0 <= d && d <= n ? fact(n) * ifact(n - d) : raw(0); }
  static finite_field binom(int n, int d) noexcept { return 0 <= d && d <= n ? factpow(n, d) * ifact(d) : raw(0); }
  static finite_field nbinom(int n, int d) noexcept {
    return n >= 0 && d >= 0 ? (n == 0 ? raw(d == 0) : binom(n + d - 1, d)) : raw(0);
  }

 private:
  unsigned v;
};

}  // namespace finite_field_impl

using finite_field_impl::finite_field;
using F_998244353 = finite_field<998244353>;
using F_1000000007 = finite_field<1000000007>;

}  // namespace mod
}  // namespace kod

namespace kod {
namespace sol {

using Fp = mod::F_998244353;

void run() {
  const int n = scan();
  const int m = scan();

  const auto a = scan_vec<int>(n);
  vector<int> c(n);
  for (const int x : a) {
    c[x] += 1;
  }
  const int min = *std::min_element(a.begin(), a.end());
  if (min * 2 > n) {
    println(0);
    return;
  }
  for (const int k : rep(min + 1, n / 2 + 1)) {
    if (c[k] != 0) {
      println(0);
      return;
    }
  }

  Fp ans = 1;
  int l = n, r = n, p = 0;
  for (const int k : revrep(n / 2 + 1, n)) {
    // {0, l - k} + {0, r - k}
    if (c[k] == l - k + r - k) {
      ans *= Fp::binom(c[k], l - k);
      l = r = k;
      p += 2;
    } else if (c[k] == l - k) {
      if (l == r) ans *= 2;
      l = k;
      p += 1;
    } else if (c[k] == r - k) {
      r = k;
      p += 1;
    } else if (c[k] != 0) {
      ans = 0;
    }
  }

  if (min * 2 == n) {
    Fp good = 0;
    for (const int x : rep(c[min] + 1)) {
      const int y = c[min] - x;
      if (l - x == min && r - y == min) {
        good += Fp::binom(c[min], x);
      }
    }
    ans *= good;
    p += 2;
  } else {
    if (std::max(l, r) - c[min] != min) {
      ans = 0;
    }
    p += 1;
  }
  ans *= Fp::binom(m, p);
  println(ans);
}

}  // namespace sol
}  // namespace kod

yukicoder

結果

テストケース

ソースコード