結果

問題 No.2336 Do you like typical problems?
ユーザー lam6er
提出日時 2025-04-09 20:58:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,691 ms / 2,000 ms
コード長 2,911 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,252 KB
実行使用メモリ 170,500 KB
最終ジャッジ日時 2025-04-09 21:00:55
合計ジャッジ時間 14,042 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    B = []
    C = []
    for _ in range(N):
        b = int(input[ptr])
        c = int(input[ptr + 1])
        B.append(b)
        C.append(c)
        ptr += 2
    
    # Precompute factorial[N] modulo MOD
    max_n = N
    factorial = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        factorial[i] = factorial[i - 1] * i % MOD
    inv_2 = pow(2, MOD - 2, MOD)
    
    # Compute sum_self
    sum_self = 0
    for i in range(N):
        b = B[i]
        c = C[i]
        len_u = c - b + 1
        if len_u == 0:
            continue
        term = 0
        if len_u > 1:
            mod_len = len_u % MOD
            numerator = (mod_len - 1) % MOD
            denom = (2 * mod_len) % MOD
            inv_denom = pow(denom, MOD - 2, MOD)
            term = (numerator * inv_denom) % MOD
        sum_self = (sum_self + term) % MOD
    
    # Generate events for line sweep
    events = []
    for i in range(N):
        b = B[i]
        c = C[i]
        len_u = c - b + 1
        if len_u == 0:
            continue
        mod_len = len_u % MOD
        inv_len = pow(mod_len, MOD - 2, MOD)
        start = b
        end = c + 1
        events.append((start, inv_len))
        events.append((end, (-inv_len) % MOD))
    
    events.sort()
    
    # Process events to form merged intervals
    merged_intervals = []
    prev_x = None
    current_A = 0
    for x, delta in events:
        if prev_x is not None and x > prev_x:
            merged_intervals.append((prev_x, x, current_A % MOD))
        current_A = (current_A + delta) % MOD
        prev_x = x
    
    # Compute sum_all = cross_part + same_part
    cross_contrib = 0
    same_contrib = 0
    prefix_sum = 0
    for s, e, a_i in merged_intervals:
        len_i = e - s
        if len_i <= 0:
            continue
        len_i_mod = len_i % MOD
        a_i_mod = a_i % MOD
        
        # cross contribution
        term = (a_i_mod * len_i_mod) % MOD
        cross_term = (term * prefix_sum) % MOD
        cross_contrib = (cross_contrib + cross_term) % MOD
        
        # update prefix_sum
        current_contrib = term
        prefix_sum = (prefix_sum + current_contrib) % MOD
        
        # same contribution
        same_pairs = (len_i * (len_i - 1) // 2) % MOD
        a_sq = (a_i_mod * a_i_mod) % MOD
        same_term = (a_sq * same_pairs) % MOD
        same_contrib = (same_contrib + same_term) % MOD
    
    sum_all = (cross_contrib + same_contrib) % MOD
    
    # Compute desired_sum = (sum_all - sum_self) mod MOD
    desired_sum = (sum_all - sum_self) % MOD
    
    # Compute factor = (factorial[N] * inv_2) % MOD
    factor = (factorial[N] * inv_2) % MOD
    
    # Compute answer
    answer = (desired_sum * factor) % MOD
    print(answer)

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