結果

問題 No.2616 中央番目の中央値
ユーザー InTheBloom
提出日時 2024-01-26 23:07:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 293 ms / 2,000 ms
コード長 2,873 bytes
コンパイル時間 1,390 ms
コンパイル使用メモリ 119,784 KB
実行使用メモリ 23,300 KB
最終ジャッジ日時 2024-09-28 08:57:59
合計ジャッジ時間 6,835 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <atcoder/segtree>
#include <vector>
#include <cassert>

using namespace std;
using namespace atcoder;
using ll = long long;

ll ModPow (ll a, ll x, const ll MOD) {
    assert(0 <= x);
    assert(1 <= MOD);

    a %= MOD;
    if (a < 0) a += MOD;

    ll res = 1;
    while (x != 0) {
        if (0 < (x & 1)) {
            res *= a;
            res %= MOD;
        }
        a *= a;
        a %= MOD;
        x >>= 1;
    }

    return res % MOD;
}

ll ModInv (ll x, const ll MOD) {
    assert(1 <= x);
    assert(2 <= MOD);
    return ModPow(x, MOD-2, MOD);
}

int ope (int a, int b) { return a + b; }
int e () { return 0; }

void solve (int N, vector<int> &P) {
    // ある要素を中央値に採用すると考える。
    // 「前から見て(長さ-1)/2個からなる部分列でmaxがそれ未満」と「後ろから見て(長さ-1)/2個からなる部分列でminがそれ超過」の場合の数がわかればよい？
    // -> 明らかにΘ(N^2)以上が見込まれるのでダメ

    // 右側から超過をk個、未満をl個とったと考える。この時、左側からとるべきものも確定して、未満をk個、超過をl個とる必要がある。
    // 左側でとった超過/未満は右側でつじつまを合わせるため、独立に考えてよい。
    // 例えば左側未満は[0, min((左側未満), (右側超過))]個自由にとれる。->どこからとるかはnCkになり、これの積を足していけばいい
    // wolfram alpha先生にbinomial(N, i) * binomial(M, i)の和[0, N]を投げたら(M+N)!/(N!M!)って言われた
    // セグ木かなんかでこれを持っておけばよくないか？

    const ll MOD = 998244353;

    vector<ll> fact(2*N+1), factinv(2*N+1);
    fact[0] = 1;
    for (int i = 1; i <= 2*N; i++) fact[i] = i*fact[i-1] % MOD;
    factinv[2*N] = ModInv(fact[2*N], MOD);
    for (int i = 2*N-1; 0 <= i; i--) factinv[i] = (i+1) * factinv[i+1] % MOD;

    segtree<int, ope, e> L(N), R(N);
    for (int i = 0; i < N; i++) R.set(i, 1);

    ll ans = 0;
    for (int i = 0; i < N; i++) {
        // 計算
        int Llarge = L.prod(P[i]+1, N);
        int Lless = L.prod(0, P[i]);
        int Rlarge = R.prod(P[i]+1, N);
        int Rless = R.prod(0, P[i]);

        ll add = fact[Llarge + Rless] * factinv[Llarge] % MOD;
        add *= factinv[Rless];
        add %= MOD;

        add *= fact[Rlarge + Lless];
        add %= MOD;
        add *= factinv[Rlarge];
        add %= MOD;
        add *= factinv[Lless];
        add %= MOD;

        ans += add;
        ans %= MOD;

        // 更新
        L.set(P[i], 1);
        R.set(P[i], 0);
    }

    cout << ans << "\n";
}

int main () {
    int N; cin >> N;
    vector<int> P(N);
    for (int i = 0; i < N; i++) {
        cin >> P[i];
        P[i]--; // 0-indexed
    }

    solve(N, P);
}
0