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

提出ソース

結果

問題	No.2616 中央番目の中央値
ユーザー	Re0denX
提出日時	2024-01-27 18:54:24
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	70 ms / 2,000 ms
コード長	5,538 bytes
コンパイル時間	2,495 ms
コンパイル使用メモリ	206,644 KB
実行使用メモリ	10,368 KB
最終ジャッジ日時	2024-01-27 18:54:50
合計ジャッジ時間	5,261 ms
ジャッジサーバーID （参考情報）	judge11 / judge13

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,548 KB
testcase_01	AC	2 ms 6,548 KB
testcase_02	AC	2 ms 6,548 KB
testcase_03	AC	2 ms 6,548 KB
testcase_04	AC	2 ms 6,548 KB
testcase_05	AC	2 ms 6,548 KB
testcase_06	AC	2 ms 6,548 KB
testcase_07	AC	2 ms 6,548 KB
testcase_08	AC	2 ms 6,548 KB
testcase_09	AC	2 ms 6,548 KB
testcase_10	AC	2 ms 6,548 KB
testcase_11	AC	2 ms 6,548 KB
testcase_12	AC	2 ms 6,548 KB
testcase_13	AC	3 ms 6,548 KB
testcase_14	AC	3 ms 6,548 KB
testcase_15	AC	4 ms 6,548 KB
testcase_16	AC	5 ms 6,548 KB
testcase_17	AC	8 ms 6,548 KB
testcase_18	AC	11 ms 6,548 KB
testcase_19	AC	21 ms 6,548 KB
testcase_20	AC	20 ms 6,548 KB
testcase_21	AC	43 ms 8,064 KB
testcase_22	AC	66 ms 10,368 KB
testcase_23	AC	66 ms 10,368 KB
testcase_24	AC	54 ms 10,368 KB
testcase_25	AC	55 ms 10,368 KB
testcase_26	AC	67 ms 10,368 KB
testcase_27	AC	66 ms 10,368 KB
testcase_28	AC	67 ms 10,368 KB
testcase_29	AC	67 ms 10,368 KB
testcase_30	AC	67 ms 10,368 KB
testcase_31	AC	67 ms 10,368 KB
testcase_32	AC	67 ms 10,368 KB
testcase_33	AC	66 ms 10,368 KB
testcase_34	AC	67 ms 10,368 KB
testcase_35	AC	70 ms 10,368 KB
testcase_36	AC	66 ms 10,368 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;
}

// @param 0-indexed Fenwick (binary indexed tree / Fenwick tree) (i : [0, len))
template <class T> struct Fenwick {
  int n;
  std::vector<T> data;
  Fenwick(int len = 0) : n(len), data(len) {}
  void reset() { std::fill(data.begin(), data.end(), T(0)); }
  void add(int pos, T v) { // a[pos] += v
    pos++;
    while (pos > 0 && pos <= n) data[pos - 1] += v, pos += pos & -pos;
  }
  T sum(int k) const { // a[0] + ... + a[k - 1]
    T res = 0;
    while (k > 0) res += data[k - 1], k -= k & -k;
    return res;
  }

  T sum(int l, int r) const { return sum(r) - sum(l); } // a[l] + ... + a[r - 1]

  int kth(T k) {
    int ret = 0;
    for (int i = 1 << std::__lg(n); i; i /= 2) 
      if (ret + i <= n && k >= data[ret + i - 1]) 
        ret += i, k -= data[ret - 1];
    return ret;
  }

  template <class OStream> friend OStream &operator<<(OStream &os, const Fenwick &bit) {
    T prv = 0;
    os << '[';
    for (int i = 1; i <= bit.n; i++) {
      T now = bit.sum(i);
      os << now - prv << ',', prv = now;
    }
    return os << ']';
  }
};

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--;
  
  Fenwick<int> ft(N);
  num ans = 0;
  Combina<num> comb(N * 2);
  for (int i = 0; i < N; i++) {
    int A = ft.sum(0, P[i]);
    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);
  }
  std::cout << ans << "\n";
}

yukicoder

結果

テストケース

ソースコード