結果

問題 No.1546 [Cherry 2nd Tune D] 思ったよりも易しくない
ユーザー lam6er
提出日時 2025-03-20 20:48:32
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,508 bytes
コンパイル時間 489 ms
コンパイル使用メモリ 82,668 KB
実行使用メモリ 170,220 KB
最終ジャッジ日時 2025-03-20 20:48:55
合計ジャッジ時間 9,278 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 TLE * 1 -- * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    entries = []
    index = 1
    Ts = []
    Vs = []
    for _ in range(N):
        T = int(data[index])
        V = int(data[index + 1]) % MOD
        Ts.append(T)
        Vs.append(V)
        index += 2
    
    # Compute M and mod values
    M = sum(Ts)
    M_mod = M % MOD
    M_plus_1_mod = (M + 1) % MOD
    
    # Precompute inverses
    inv2 = pow(2, MOD - 2, MOD)
    inv6 = pow(6, MOD - 2, MOD)
    inv4 = pow(4, MOD - 2, MOD)
    
    ans = 0
    current_cum = 0
    
    for i in range(N):
        T_i = Ts[i]
        V_i = Vs[i]
        
        s = current_cum + 1
        e = current_cum + T_i
        
        a = s
        b = e
        
        # Compute sum_k from a to b
        a1 = (a - 1) % MOD
        term1_b = (b % MOD) * ((b + 1) % MOD) % MOD
        term1 = term1_b * inv2 % MOD
        term2_a = a1 * (a % MOD) % MOD
        term2 = term2_a * inv2 % MOD
        sumk = (term1 - term2) % MOD
        
        # Compute sum_k^2 from a to b
        term1_b_k2 = ((b % MOD) * ((b + 1) % MOD) % MOD) * ((2 * b + 1) % MOD) % MOD
        term1_k2 = term1_b_k2 * inv6 % MOD
        
        a_minus_1 = a - 1
        a_minus_1_mod = a_minus_1 % MOD
        a_mod = a % MOD
        two_a_minus_1_plus_1 = (2 * a_minus_1 + 1) % MOD
        term2_a_k2 = (a_minus_1_mod * a_mod % MOD) * two_a_minus_1_plus_1 % MOD
        term2_k2 = term2_a_k2 * inv6 % MOD
        sumk2 = (term1_k2 - term2_k2) % MOD
        
        # Compute sum_k^3 from a to b
        b_sq = pow(b, 2, MOD)
        b_plus_1_sq = pow(b + 1, 2, MOD)
        term1_k3 = (b_sq * b_plus_1_sq) % MOD
        term1_k3 = term1_k3 * inv4 % MOD
        
        a_minus_1_sq = pow(a_minus_1, 2, MOD)
        a_minus_1_plus_1_sq = pow(a_minus_1 + 1, 2, MOD)
        term2_k3 = (a_minus_1_sq * a_minus_1_plus_1_sq) % MOD
        term2_k3 = term2_k3 * inv4 % MOD
        sumk3 = (term1_k3 - term2_k3) % MOD
        
        # Calculate the terms
        term_M = (M_mod * sumk2) % MOD
        term_M_plus_1 = (M_plus_1_mod * sumk) % MOD
        total = (term_M + term_M_plus_1 - sumk3) % MOD
        
        # Apply the division by 2 (multiply by inv2)
        total = total * inv2 % MOD
        
        # Apply Vi
        contribution = (total * V_i) % MOD
        
        ans = (ans + contribution) % MOD
        
        current_cum = e
    
    print(ans % MOD)

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