結果
問題 |
No.1552 Simple Dice Game
|
ユーザー |
![]() |
提出日時 | 2025-03-20 18:49:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 793 ms / 2,500 ms |
コード長 | 2,061 bytes |
コンパイル時間 | 228 ms |
コンパイル使用メモリ | 81,828 KB |
実行使用メモリ | 71,800 KB |
最終ジャッジ日時 | 2025-03-20 18:50:57 |
合計ジャッジ時間 | 10,263 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
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()