結果
問題 |
No.3119 A Little Cheat
|
ユーザー |
|
提出日時 | 2025-04-19 19:46:47 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,173 bytes |
コンパイル時間 | 373 ms |
コンパイル使用メモリ | 12,160 KB |
実行使用メモリ | 32,832 KB |
最終ジャッジ日時 | 2025-04-19 19:47:04 |
合計ジャッジ時間 | 16,938 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | AC * 3 WA * 46 |
ソースコード
import sys import threading def main(): import sys data = sys.stdin.read().split() it = iter(data) N = int(next(it)) M = int(next(it)) A = [0] * N for i in range(N): A[i] = int(next(it)) mod = 998244353 # Precompute M^N and M^(N-1) powM_N = pow(M, N, mod) powM_N_1 = pow(M, N-1, mod) # Sum of f_no_swap over all B: sum_i (M - A_i) * M^(N-1) sum_no_swap = 0 for ai in A: sum_no_swap = (sum_no_swap + (M - ai) % mod) % mod sum_no_swap = sum_no_swap * powM_N_1 % mod # DP to count T0: number of B with no beneficial swap anywhere # DP_i represented by two values: val1 for y not in Y_prev, val0 for y in Y_prev val1 = 1 # DP_1(y) = 1 for all y val0 = 0 # unused when size_y_prev = 0 size_y_prev = 0 l_prev = 1; r_prev = 0 # empty interval for i in range(N-1): ai = A[i]; aj = A[i+1] if ai < aj: lx, rx = 1, ai ly, ry = ai+1, aj elif ai > aj: lx, rx = aj+1, ai ly, ry = 1, aj else: lx, rx = 1, 0 # empty ly, ry = 1, 0 # empty size_x = max(0, rx - lx + 1) size_y = max(0, ry - ly + 1) # Sum of DP_i over all y S = (val1 * (M - size_y_prev) + val0 * size_y_prev) % mod # Compute overlap of X_i with previous Y_prev # X interval [lx,rx], Y_prev [l_prev, r_prev] lo = max(lx, l_prev) hi = min(rx, r_prev) overlap = max(0, hi - lo + 1) # Sum of DP_i over x in X_i preSum_X = (val1 * (size_x - overlap) + val0 * overlap) % mod # Update DP values val0_new = (S - preSum_X) % mod val1_new = S # Update for next iteration val0, val1 = val0_new, val1_new size_y_prev = size_y l_prev, r_prev = ly, ry # After DP, total sequences without any beneficial swap T0 = (val1 * (M - size_y_prev) + val0 * size_y_prev) % mod # Number of sequences with any beneficial swap total = powM_N S1 = (total - T0) % mod # Final answer ans = (sum_no_swap + S1) % mod print(ans) if __name__ == '__main__': main()