結果
問題 |
No.3119 A Little Cheat
|
ユーザー |
|
提出日時 | 2025-04-19 19:42:52 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,822 bytes |
コンパイル時間 | 524 ms |
コンパイル使用メモリ | 12,288 KB |
実行使用メモリ | 43,424 KB |
最終ジャッジ日時 | 2025-04-19 19:43:11 |
合計ジャッジ時間 | 18,538 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | AC * 3 WA * 46 |
ソースコード
import sys def main(): data = sys.stdin.read().split() N = int(data[0]); M = int(data[1]) A = list(map(int, data[2:2+N])) mod = 998244353 # Precompute M^(N-1) and M^N mod M_pow_N_1 = pow(M, N-1, mod) M_pow_N = M_pow_N_1 * M % mod # Sum of initial matches over all B: sum_i (M - A_i) * M^(N-1) sum1 = 0 for a in A: sum1 = (sum1 + (M - a) % mod) % mod sum1 = sum1 * M_pow_N_1 % mod # If no swap is possible if N == 1: print(sum1) return # Prepare intervals I_i = (min(A_i, A_{i+1}), max(A_i, A_{i+1})) L = [0] * (N-1) R = [0] * (N-1) d = [0] * (N-1) for i in range(N-1): u, v = A[i], A[i+1] if u < v: L[i], R[i] = u, v else: L[i], R[i] = v, u d[i] = R[i] - L[i] # <-- typo removed # DP over intervals: state is count of sequences where B_i in I_i (1) or not (0) d0 = d[0] dp0 = [(M - d0) % mod, d0 % mod] for i in range(N-2): Li, Ri, di = L[i], R[i], d[i] Lj, Rj, dj = L[i+1], R[i+1], d[i+1] inter = max(0, min(Ri, Rj) - max(Li, Lj)) size11 = inter size10 = di - inter size01 = dj - inter size00 = M - (size11 + size10 + size01) T00, T01 = size00 % mod, size01 % mod T10, T11 = size10 % mod, size11 % mod dp1_0 = (dp0[0] * T00 + dp0[1] * T10) % mod dp1_1 = (dp0[0] * T01 + dp0[1] * T11) % mod dp0 = [dp1_0, dp1_1] # Final position N: match same state d_last = d[N-2] cnt_end0 = (M - d_last) % mod cnt_end1 = d_last % mod total_no_swap_gain = (dp0[0] * cnt_end0 + dp0[1] * cnt_end1) % mod extra = (M_pow_N - total_no_swap_gain) % mod answer = (sum1 + extra) % mod print(answer) if __name__ == '__main__': main()