結果

問題 No.3119 A Little Cheat
ユーザー Mistletoe
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0