結果

問題 No.1761 Sequence Distance
ユーザー 已经死了
提出日時 2025-07-27 22:15:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,303 bytes
コンパイル時間 350 ms
コンパイル使用メモリ 82,324 KB
実行使用メモリ 307,920 KB
最終ジャッジ日時 2025-07-27 22:16:08
合計ジャッジ時間 20,215 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other AC * 1 WA * 19 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

MI=lambda:map(int,input().split())
li=lambda:list(MI())
ii=lambda:int(input())
mod=998244353
n,m=MI()
# dp[d][s]: 当前在某步，|D|=d，累计面积=s 的方案数
# 0 ≤ d ≤ m, 0 ≤ s ≤ m
dp=[[0]*(m+1) for _ in range(m+2)]
dp[0][0]=1
for j in range(n):
    ndp=[ [0]*(m+1) for _ in range(m+2) ]
    # 只需要枚举 d 到 min(j, m)
    lim = min(j, m)
    # 但无论 j，d 最多到 m
    for d in range(lim+1):
        row=dp[d]
        if not any(row): continue
        # Δ=0（水平步，两种类型，共 weight=2），新 |D|=d，area +d
        w2=2
        add=d
        for s in range(m-add+1):
            v=row[s]
            if v:
                ndp[d][s+add]=(ndp[d][s+add] + v*w2) % mod
        # Δ=+1，上升，新 |D|=d+1，area +d+1，weight=1
        add=d+1
        if add<=m:
            for s in range(m-add+1):
                v=row[s]
                if v:
                    ndp[d+1][s+add]=(ndp[d+1][s+add] + v) % mod
        # Δ=-1，下降，新 |D|=d-1（仅当 d>0），area +d-1，weight=1
        if d>0:
            add=d-1
            for s in range(m-add+1):
                v=row[s]
                if v:
                    ndp[d-1][s+add]=(ndp[d-1][s+add] + v) % mod
    dp=ndp
# 最后要求回到 D=0 且面积正好为 m
print(dp[0][m] % mod)
0