結果
問題 | No.2356 Back Door Tour in Four Seasons |
ユーザー |
![]() |
提出日時 | 2025-03-31 17:41:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 250 ms / 2,000 ms |
コード長 | 1,278 bytes |
コンパイル時間 | 299 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 134,912 KB |
最終ジャッジ日時 | 2025-03-31 17:43:14 |
合計ジャッジ時間 | 7,939 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 28 |
ソースコード
MOD = 998244353 def main(): import sys input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 sum_A = 0 U = [] F = [] W = [] P_count = 0 for _ in range(N): S_i = input[ptr] A_i = int(input[ptr+1]) ptr += 2 sum_A += A_i if S_i == 'U': U.append(A_i) elif S_i == 'F': F.append(A_i) elif S_i == 'W': W.append(A_i) elif S_i == 'P': P_count += 1 # Compute inv(N-1) inv_N_1 = pow(N-1, MOD-2, MOD) if (N-1) != 0 else 0 # base = (N-2) / (N-1) mod MOD base = ( ( (N - 2) % MOD ) * inv_N_1 ) % MOD def compute_sum(As): res = 0 for a in As: x = pow(base, a, MOD) term = (1 - x) % MOD res = (res + term) % MOD return res u_sum = compute_sum(U) f_sum = compute_sum(F) w_sum = compute_sum(W) # Compute sum_S sum_S = u_sum * f_sum % MOD sum_S = sum_S * w_sum % MOD sum_S = sum_S * P_count % MOD # Compute P = (N-1)^sum_A mod MOD P = pow(N-1, sum_A, MOD) # Answer is (P * sum_S) mod MOD print((P * sum_S) % MOD) if __name__ == '__main__': main()