結果

問題 No.3119 A Little Cheat
コンテスト
ユーザー detteiuu
提出日時 2026-10-03 03:28:41
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 627 ms / 2,000 ms
+ 7µs
コード長 1,260 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 62 ms
コンパイル使用メモリ 83,324 KB
実行使用メモリ 116,428 KB
最終ジャッジ日時 2026-10-03 03:29:13
合計ジャッジ時間 26,425 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import defaultdict

MOD = 998244353

N, M = map(int, input().split())
A = list(map(int, input().split()))

dp = defaultdict(int)
ndp = defaultdict(int)
l, r = min(A[0], A[1]), max(A[0], A[1])
dp[(1, l)] = l%MOD
dp[(l+1, r)] = (r-l)%MOD
dp[(r+1, M)] = (M-r)%MOD
for i in range(1, N):
    ndp = defaultdict(int)
    C = []
    D = []
    for j in range(-1, 2):
        if 0 <= i+j < N:
            D.append(A[i+j])
    D.sort()
    C.append((1, D[0]))
    for j in range(1, len(D)):
        C.append((C[-1][1]+1, D[j]))
    C.append((C[-1][1]+1, M))
    for (l1, r1), c in dp.items():
        for l2, r2 in C:
            if (l1, r1, l2, r2, i) == (2, 2, 1, 1, 2):
                pass
            if r1 <= A[i-1] and r2 <= A[i] and (A[i-1] < l2 or A[i] < l1):
                continue
            if r1 <= A[i-1] and A[i] < l2 and A[i] < l1 and A[i-1] < l2:
                continue
            if A[i-1] < l1 and r2 <= A[i] and A[i-1] < l2 and A[i] < l1:
                continue
            ndp[(l2, r2)] += c*(r2-l2+1)%MOD
            ndp[(l2, r2)] %= MOD
    dp, ndp = ndp, dp

ans = 0
p = pow(M, N-1, MOD)
for a in A:
    ans += (M-a)*p%MOD
    ans %= MOD
ans += pow(M, N, MOD)
ans %= MOD
ans -= sum(dp.values())%MOD
ans %= MOD

print(ans)
0