結果

問題 No.2327 Inversion Sum
ユーザー lam6er
提出日時 2025-03-20 20:30:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 304 ms / 2,000 ms
コード長 2,696 bytes
コンパイル時間 200 ms
コンパイル使用メモリ 82,420 KB
実行使用メモリ 111,604 KB
最終ジャッジ日時 2025-03-20 20:32:02
合計ジャッジ時間 5,650 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1

    fixed = []
    p_set = set()
    k_set = set()
    for _ in range(M):
        P = int(input[ptr])
        ptr += 1
        K = int(input[ptr])
        ptr += 1
        fixed.append((P, K))
        p_set.add(P)
        k_set.add(K)

    # Precompute factorials
    max_fact = N
    fact = [1] * (max_fact + 1)
    for i in range(1, max_fact + 1):
        fact[i] = fact[i - 1] * i % MOD

    inv_2 = (MOD + 1) // 2  # 499122177

    # Compute A (inversions among fixed elements)
    fixed_sorted = sorted(fixed, key=lambda x: x[1])  # sort by K
    P_list = [p for p, k in fixed_sorted]
    A = 0
    if M > 0:
        class FenwickTree:
            def __init__(self, size):
                self.n = size
                self.tree = [0] * (self.n + 2)

            def update(self, idx, delta=1):
                while idx <= self.n:
                    self.tree[idx] += delta
                    idx += idx & -idx

            def query(self, idx):
                res = 0
                while idx > 0:
                    res += self.tree[idx]
                    idx -= idx & -idx
                return res

        max_P = N
        bit = FenwickTree(max_P)
        for i, p in enumerate(P_list):
            cnt = bit.query(p)
            A = (A + i - cnt) % MOD
            bit.update(p)

    T = N - M
    sum_A = A * fact[T] % MOD

    # Compute sum_B
    sum_contrib = 0
    S = []
    for x in range(1, N + 1):
        if x not in p_set:
            S.append(x)
    S_sorted = sorted(S)

    T_list = []
    for x in range(1, N + 1):
        if x not in k_set:
            T_list.append(x)
    T_sorted = sorted(T_list)

    for p, k in fixed:
        # compute R_p and S_p (count in T_sorted)
        pos = bisect.bisect_left(T_sorted, k)
        S_p = pos
        R_p = len(T_sorted) - bisect.bisect_right(T_sorted, k)

        # compute C_less_p and C_greater_p in S_sorted
        C_less = bisect.bisect_left(S_sorted, p)
        C_greater = len(S_sorted) - bisect.bisect_right(S_sorted, p)
        term = (R_p * C_less + S_p * C_greater) % MOD
        sum_contrib = (sum_contrib + term) % MOD

    if T == 0:
        sum_B = 0
    else:
        sum_B = sum_contrib * fact[T - 1] % MOD

    # Compute sum_C
    if T <= 1:
        sum_C = 0
    else:
        part1 = T * (T - 1) % MOD
        part1 = part1 * inv_2 % MOD
        part2 = fact[T] * inv_2 % MOD
        sum_C = part1 * part2 % MOD

    total = (sum_A + sum_B + sum_C) % MOD
    print(total)

if __name__ == "__main__":
    main()
0