#947057 (C++17) No.2616 中央番目の中央値

提出ソース

結果

問題	No.2616 中央番目の中央値
ユーザー	Re0denX
提出日時	2024-01-27 19:47:25
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	70 ms / 2,000 ms
コード長	8,963 bytes
コンパイル時間	2,175 ms
コンパイル使用メモリ	207,480 KB
実行使用メモリ	10,304 KB
最終ジャッジ日時	2024-09-28 09:48:28
合計ジャッジ時間	4,664 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	3 ms 6,944 KB
testcase_15	AC	4 ms 6,940 KB
testcase_16	AC	5 ms 6,944 KB
testcase_17	AC	7 ms 6,944 KB
testcase_18	AC	11 ms 6,940 KB
testcase_19	AC	20 ms 6,940 KB
testcase_20	AC	20 ms 6,940 KB
testcase_21	AC	43 ms 7,936 KB
testcase_22	AC	64 ms 10,240 KB
testcase_23	AC	65 ms 10,112 KB
testcase_24	AC	54 ms 10,240 KB
testcase_25	AC	54 ms 10,240 KB
testcase_26	AC	64 ms 10,112 KB
testcase_27	AC	64 ms 10,188 KB
testcase_28	AC	64 ms 10,240 KB
testcase_29	AC	66 ms 10,108 KB
testcase_30	AC	67 ms 10,240 KB
testcase_31	AC	66 ms 10,112 KB
testcase_32	AC	65 ms 10,240 KB
testcase_33	AC	67 ms 10,240 KB
testcase_34	AC	67 ms 10,240 KB
testcase_35	AC	64 ms 10,112 KB
testcase_36	AC	70 ms 10,304 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>

#ifdef LOCAl 
#include "../library/misc/debug.h"
#else 
#define debug(...) 42
#endif // LOCAL

using namespace std;
template <class T> struct Combina {
  int n;
  std::vector<T> fact, invfact;
 
  Combina() {}
  Combina(int _n) : n(_n), fact(_n + 1), invfact(_n + 1) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++)
      fact[i] = fact[i - 1] * i;
    invfact[n] = 1 / fact[n];
    for (int i = n; i >= 1; i--)
      invfact[i - 1] = invfact[i] * i;
  }
 
  T binom(int a, int b) {
    if (a < b || b < 0)
      return 0;
    return fact[a] * invfact[b] * invfact[a - b];
  }
 
  long long lucas(long long n, long long m, long long p) {
    if (n > 0 || m > 0)
      return lucas(n / p, m / p, p) * lucas(n % p, m % p, p) % p;
    else
      return 1ll;
  }
};

template <typename T> T mod_inv_in_range(T a, T m) {
  // assert(0 <= a && a < m);
  T x = a, y = m;
  // coeff of a in x and y
  T vx = 1, vy = 0;
  while (x) {
    T k = y / x;
    y %= x;
    vy -= k * vx;
    std::swap(x, y);
    std::swap(vx, vy);
  }
  assert(y == 1);
  return vy < 0 ? m + vy : vy;
}

template <typename T> struct extended_gcd_result {
  T gcd;
  T coeff_a, coeff_b;
};
template <typename T> extended_gcd_result<T> extended_gcd(T a, T b) {
  T x = a, y = b;
  // coeff of a and b in x and y
  T ax = 1, ay = 0;
  T bx = 0, by = 1;
  while (x) {
    T k = y / x;
    y %= x;
    ay -= k * ax;
    by -= k * bx;
    std::swap(x, y);
    std::swap(ax, ay);
    std::swap(bx, by);
  }
  return {y, ay, by};
}

template <typename T> T mod_inv(T a, T m) {
  a %= m;
  a = a < 0 ? a + m : a;
  return mod_inv_in_range(a, m);
}

template <int MOD_> struct modnum {
  static constexpr int MOD = MOD_;
  static_assert(MOD_ > 0, "MOD must be positive");

private:
  int v;

public:

  modnum() : v(0) {}
  modnum(int64_t v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
  explicit operator int() const { return v; }
  friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
  friend std::istream& operator >> (std::istream& in, modnum& n) { int64_t v_; in >> v_; n = modnum(v_); return in; }

  friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
  friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

  modnum inv() const {
    modnum res;
    res.v = mod_inv_in_range(v, MOD);
    return res;
  }
  friend modnum inv(const modnum& m) { return m.inv(); }
  modnum neg() const {
    modnum res;
    res.v = v ? MOD-v : 0;
    return res;
  }
  friend modnum neg(const modnum& m) { return m.neg(); }

  modnum operator- () const {
    return neg();
  }
  modnum operator+ () const {
    return modnum(*this);
  }

  modnum& operator ++ () {
    v ++;
    if (v == MOD) v = 0;
    return *this;
  }
  modnum& operator -- () {
    if (v == 0) v = MOD;
    v --;
    return *this;
  }
  modnum& operator += (const modnum& o) {
    v -= MOD-o.v;
    v = (v < 0) ? v + MOD : v;
    return *this;
  }
  modnum& operator -= (const modnum& o) {
    v -= o.v;
    v = (v < 0) ? v + MOD : v;
    return *this;
  }
  modnum& operator *= (const modnum& o) {
    v = int(int64_t(v) * int64_t(o.v) % MOD);
    return *this;
  }
  modnum& operator /= (const modnum& o) {
    return *this *= o.inv();
  }

  friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
  friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
  friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
  friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
  friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
  friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};

template <typename T> T pow(T a, long long b) {
  assert(b >= 0);
  T r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;
}

/** Binary-indexed tree
 *
 *  A binary indexed tree with N nodes of type T provides the
 *  following two functions for 0 <= i <= N:
 *
 *      prefix(int i) -> prefix_iterator<T>
 *      suffix(int i) -> suffix_iterator<T>
 *
 *  such that size(suffix(i) intersect prefix(j)) = (1 if i < j else 0).
 *  Furthermore, the resulting lists always have size at most log_2(N).
 *
 *  This can be used to implement either point-update/(prefix|suffix)-query or
 *  (prefix|suffix)-update/point-query over a virtual array of size N of a
 *  commutative monoid. This can be generalized to implement
 *  point-update/range-query or range-update/point-query over a virtual array
 *  of size N of a commutative group.
 *
 *  With 0-indexed data, prefixes are more natural:
 *   * For range update/query, use for_prefix for the ranges and for_suffix for the points.
 *   * For prefix update/query, no change.
 *   * For suffix update/query, use for_prefix(point + 1); 1-index the data.
 */
template <typename T> class binary_indexed_tree {
private:
	std::vector<T> dat;
public:
	binary_indexed_tree() {}
	explicit binary_indexed_tree(size_t N) : dat(N) {}
	binary_indexed_tree(size_t N, const T& t) : dat(N, t) {}
 
	size_t size() const { return dat.size(); }
	const std::vector<T>& data() const { return dat; }
	std::vector<T>& data() { return dat; }
 
private:
	template <typename I, typename S = I> struct iterator_range {
	private:
		I begin_;
		S end_;
	public:
		iterator_range() : begin_(), end_() {}
		iterator_range(const I& begin__, const S& end__) : begin_(begin__), end_(end__) {}
		iterator_range(I&& begin__, S&& end__) : begin_(begin__), end_(end__) {}
		I begin() const { return begin_; }
		S end() const { return end_; }
	};
 
public:
	class const_suffix_iterator {
	private:
		const T* dat;
		int a;
		const_suffix_iterator(const T* dat_, int a_) : dat(dat_), a(a_) {}
		friend class binary_indexed_tree;
	public:
		friend bool operator != (const const_suffix_iterator& i, const const_suffix_iterator& j) {
			assert(j.dat == nullptr);
			return i.a < j.a;
		}
		const_suffix_iterator& operator ++ () {
			a |= a+1;
			return *this;
		}
		const T& operator * () const {
			return dat[a];
		}
	};
	using const_suffix_range = iterator_range<const_suffix_iterator>;
	const_suffix_range suffix(int a) const {
		assert(0 <= a && a <= int(dat.size()));
		return const_suffix_range{const_suffix_iterator{dat.data(), a}, const_suffix_iterator{nullptr, int(dat.size())}};
	}
 
	class suffix_iterator {
	private:
		T* dat;
		int a;
		suffix_iterator(T* dat_, int a_) : dat(dat_), a(a_) {}
		friend class binary_indexed_tree;
	public:
		friend bool operator != (const suffix_iterator& i, const suffix_iterator& j) {
			assert(j.dat == nullptr);
			return i.a < j.a;
		}
		suffix_iterator& operator ++ () {
			a |= a+1;
			return *this;
		}
		T& operator * () const {
			return dat[a];
		}
	};
	using suffix_range = iterator_range<suffix_iterator>;
	suffix_range suffix(int a) {
		assert(0 <= a && a <= int(dat.size()));
		return suffix_range{suffix_iterator{dat.data(), a}, suffix_iterator{nullptr, int(dat.size())}};
	}
 
	class const_prefix_iterator {
	private:
		const T* dat;
		int a;
		const_prefix_iterator(const T* dat_, int a_) : dat(dat_), a(a_) {}
		friend class binary_indexed_tree;
	public:
		friend bool operator != (const const_prefix_iterator& i, const const_prefix_iterator& j) {
			assert(j.dat == nullptr);
			return i.a > 0;
		}
		const_prefix_iterator& operator ++ () {
			a &= a-1;
			return *this;
		}
		const T& operator * () const {
			return dat[a-1];
		}
	};
	using const_prefix_range = iterator_range<const_prefix_iterator>;
	const_prefix_range prefix(int a) const {
		return const_prefix_range{const_prefix_iterator{dat.data(), a}, const_prefix_iterator{nullptr, 0}};
	}
 
	class prefix_iterator {
	private:
		T* dat;
		int a;
		prefix_iterator(T* dat_, int a_) : dat(dat_), a(a_) {}
		friend class binary_indexed_tree;
	public:
		friend bool operator != (const prefix_iterator& i, const prefix_iterator& j) {
			assert(j.dat == nullptr);
			return i.a > 0;
		}
		prefix_iterator& operator ++ () {
			a &= a-1;
			return *this;
		}
		T& operator * () const {
			return dat[a-1];
		}
	};
	using prefix_range = iterator_range<prefix_iterator>;
	prefix_range prefix(int a) {
		return prefix_range{prefix_iterator{dat.data(), a}, prefix_iterator{nullptr, 0}};
	}
};

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  using num = modnum<998244353>;
  int N; std::cin >> N;
  std::vector<int> P(N);
  for (auto &x : P) std::cin >> x, x--;
  
  binary_indexed_tree<int> bit(N);
  num ans = 0;
  Combina<num> comb(N * 2);
  for (int i = 0; i < N; i++) {
    int A = 0;
    for (auto &x : bit.prefix(P[i] + 1)) A += x;
    int B = i - A;
    int C = N - i - 1 - P[i] + A;
    int D = P[i] - A;
    assert(A + B + C + D == N - 1);
    ans += comb.binom(A + C, A) * comb.binom(B + D, B);
    // ft.add(P[i], 1);
    for (auto &x : bit.suffix(P[i])) x++;
  }
  std::cout << ans << "\n";
}

yukicoder

結果

テストケース

ソースコード