結果

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

ソースコード

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 r1 <= A[i-1] and r2 <= A[i] and (r1 < l2 or r2 < 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