結果

問題 No.2616 中央番目の中央値
ユーザー InTheBloomInTheBloom
提出日時 2024-01-26 23:07:34
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 296 ms / 2,000 ms
コード長 2,873 bytes
コンパイル時間 1,235 ms
コンパイル使用メモリ 121,652 KB
実行使用メモリ 23,288 KB
最終ジャッジ日時 2024-01-26 23:07:49
合計ジャッジ時間 7,499 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 AC 2 ms
6,676 KB
testcase_05 AC 2 ms
6,676 KB
testcase_06 AC 1 ms
6,676 KB
testcase_07 AC 2 ms
6,676 KB
testcase_08 AC 2 ms
6,676 KB
testcase_09 AC 2 ms
6,676 KB
testcase_10 AC 2 ms
6,676 KB
testcase_11 AC 2 ms
6,676 KB
testcase_12 AC 2 ms
6,676 KB
testcase_13 AC 4 ms
6,676 KB
testcase_14 AC 5 ms
6,676 KB
testcase_15 AC 8 ms
6,676 KB
testcase_16 AC 16 ms
6,676 KB
testcase_17 AC 24 ms
6,676 KB
testcase_18 AC 41 ms
6,676 KB
testcase_19 AC 93 ms
9,352 KB
testcase_20 AC 84 ms
9,352 KB
testcase_21 AC 177 ms
15,304 KB
testcase_22 AC 270 ms
23,208 KB
testcase_23 AC 274 ms
23,288 KB
testcase_24 AC 223 ms
23,288 KB
testcase_25 AC 251 ms
23,288 KB
testcase_26 AC 270 ms
23,288 KB
testcase_27 AC 271 ms
23,288 KB
testcase_28 AC 270 ms
23,288 KB
testcase_29 AC 296 ms
23,288 KB
testcase_30 AC 271 ms
23,288 KB
testcase_31 AC 270 ms
23,288 KB
testcase_32 AC 270 ms
23,288 KB
testcase_33 AC 296 ms
23,288 KB
testcase_34 AC 269 ms
23,288 KB
testcase_35 AC 271 ms
23,288 KB
testcase_36 AC 278 ms
23,288 KB
権限があれば一括ダウンロードができます

ソースコード

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