結果

問題 No.2336 Do you like typical problems?
コンテスト
ユーザー detteiuu
提出日時 2026-07-27 22:57:43
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,342 ms / 2,000 ms
+ 735µs
コード長 1,399 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 233 ms
コンパイル使用メモリ 96,232 KB
実行使用メモリ 223,968 KB
最終ジャッジ日時 2026-07-27 22:57:58
合計ジャッジ時間 13,300 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from sys import stdin
input = stdin.readline
from collections import defaultdict

def factorial(n):
    F = [1]
    for i in range(1, n+1):
        F.append(F[-1]*i%MOD)
    invF = [pow(F[-1], -1, MOD)]
    for i in reversed(range(n)):
        invF.append(invF[-1]*(i+1)%MOD)
    invF = invF[::-1]
    return F, invF

def inverse(n, d):
    return n * pow(d, -1, MOD) % MOD

MOD = 998244353
F, invF = factorial(10**6)

def nC2(n):
    return inverse(n*(n-1)%MOD, 2)
def nC3(n):
    return n*(n-1)*(n-2)//6

N = int(input())
BC = [list(map(int, input().split())) for _ in range(N)]

D = defaultdict(int)
for B, C in BC:
    D[C-B+1] = inverse(1, C-B+1)

event = []
for B, C in BC:
    event.append((0, B, C+1))
    event.append((1, C+1, B))
event.sort(key=lambda x:(x[1], -x[0]))
idx = 0
SUM = 0
SUM2 = 0
res = 0
while idx < len(event):
    n = event[idx][1]
    while idx < len(event) and event[idx][1] == n:
        t, l, r = event[idx]
        if t == 0:
            SUM += SUM2*D[r-l]%MOD
            SUM %= MOD
            SUM2 += D[r-l]
            SUM2 %= MOD
        else:
            l, r = r, l
            SUM2 -= D[r-l]
            SUM2 %= MOD
            SUM -= SUM2*D[r-l]%MOD
            SUM %= MOD
        idx += 1
    if idx == len(event): break
    nex = event[idx][1]
    cnt = nex-n
    res += SUM*cnt%MOD
    res %= MOD

res2 = inverse(1, 2)*(nC2(N)-res)%MOD
print(res2*F[N]%MOD)
0