結果

問題 No.1546 [Cherry 2nd Tune D] 思ったよりも易しくない
ユーザー lam6er
提出日時 2025-03-31 17:20:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 305 ms / 2,000 ms
コード長 1,915 bytes
コンパイル時間 334 ms
コンパイル使用メモリ 82,556 KB
実行使用メモリ 151,392 KB
最終ジャッジ日時 2025-03-31 17:22:17
合計ジャッジ時間 16,095 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

# Precompute inverse values for 2, 6
inv2 = pow(2, MOD - 2, MOD)
inv6 = pow(6, MOD - 2, MOD)

def sum1_mod(x):
    x_mod = x % MOD
    return x_mod * (x_mod + 1) % MOD * inv2 % MOD

def sum2_mod(x):
    x_mod = x % MOD
    a = x_mod
    b = (x_mod + 1) % MOD
    c = (2 * x_mod + 1) % MOD
    return a * b % MOD * c % MOD * inv6 % MOD

def sum3_mod(x):
    s1 = sum1_mod(x)
    return s1 * s1 % MOD

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    blocks = []
    total_m = 0
    for _ in range(n):
        t = int(input[ptr])
        v = int(input[ptr+1])
        ptr +=2
        blocks.append((t, v))
        total_m += t
    
    M_mod = total_m % MOD
    M_plus_1_mod = (total_m + 1) % MOD
    
    ans = 0
    prev_total = 0
    for t, v in blocks:
        a = prev_total + 1
        b = prev_total + t
        prev_total += t
        
        a_s = a
        b_s = b
        
        # Compute sum1: sum of k from a to b
        sum1_b = sum1_mod(b_s)
        sum1_a_1 = sum1_mod(a_s - 1)
        s1 = (sum1_b - sum1_a_1) % MOD
        
        # Compute sum2: sum of k^2 from a to b
        sum2_b = sum2_mod(b_s)
        sum2_a_1 = sum2_mod(a_s - 1)
        s2 = (sum2_b - sum2_a_1) % MOD
        
        # Compute sum3: sum of k^3 from a to b
        sum3_b = sum3_mod(b_s)
        sum3_a_1 = sum3_mod(a_s - 1)
        s3 = (sum3_b - sum3_a_1) % MOD
        
        # Calculate the terms
        term1 = (M_plus_1_mod * s1) % MOD
        term2 = (M_mod * s2) % MOD
        term3 = s3 % MOD
        
        total_term = (term1 + term2 - term3) % MOD
        total_term = (total_term * inv2) % MOD  # multiply by inverse of 2
        
        # Multiply by v and accumulate
        contribution = (total_term * v) % MOD
        ans = (ans + contribution) % MOD
    
    print(ans)

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