結果

問題 No.1552 Simple Dice Game
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:23:09
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 789 ms / 2,500 ms
コード長 2,061 bytes
コンパイル時間 181 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 71,804 KB
最終ジャッジ日時 2025-03-20 20:25:12
合計ジャッジ時間 10,022 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    N, M = map(int, sys.stdin.readline().split())
    if M == 1:
        print(0)
        return
    
    MOD_phi = MOD - 1
    effective_e_plus = (N + 1) % MOD_phi
    effective_e_minus = (N - 1) % MOD_phi
    
    pow_n_plus_1 = [0] * (M + 1)
    pow_n_minus_1 = [0] * (M + 1)
    
    for m in range(1, M + 1):
        pow_n_plus_1[m] = pow(m, effective_e_plus, MOD)
        pow_n_minus_1[m] = pow(m, effective_e_minus, MOD)
    
    # Compute Term1: sum(m^(n+1) for m in 1..M)
    Term1 = 0
    for m in range(1, M + 1):
        Term1 = (Term1 + pow_n_plus_1[m]) % MOD
    
    # Compute Term2
    Term2 = 0
    inv2 = pow(2, MOD-2, MOD)
    for m in range(2, M + 1):
        part1 = (m * m % MOD) * (m - 1) % MOD
        part1 = part1 * inv2 % MOD
        a = pow_n_minus_1[m]
        b = pow_n_minus_1[m-1]
        part2 = (a - b) % MOD
        term = part1 * part2 % MOD
        Term2 = (Term2 + term) % MOD
    
    # Compute Term3: sum(t^2 * (M - t +1)^(n-1))
    Term3 = 0
    for t in range(1, M + 1):
        m = M - t + 1
        exponent = pow_n_minus_1[m]
        term = (t * t % MOD) * exponent % MOD
        Term3 = (Term3 + term) % MOD
    
    # Compute Term4: sum over t=1..M-1
    Term4 = 0
    for t in range(1, M):  # t from 1 to M-1 inclusive
        sum_s_num = t + 1 + M
        sum_s_num_mod = sum_s_num % MOD
        count_mod = (M - t) % MOD
        sum_s_mod = sum_s_num_mod * count_mod % MOD
        sum_s_mod = sum_s_mod * inv2 % MOD
        
        current_m = (M - t) + 1
        previous_m = M - t
        a = pow_n_minus_1[current_m]
        b = pow_n_minus_1[previous_m]
        delta = (a - b) % MOD
        
        term = (t % MOD) * sum_s_mod % MOD
        term = term * delta % MOD
        Term4 = (Term4 + term) % MOD
    
    total_max = (Term1 + Term2) % MOD
    total_min = (Term3 + Term4) % MOD
    result = (total_max - total_min) % MOD
    
    n_mod = N % MOD
    result = (result * n_mod) % MOD
    print((result + MOD) % MOD)

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