Day 169-Q3 — 2026-10-04 | 隣接差の総和がちょうど K の順列（連結成分 DP＝挿入 DP。値を小さい順に置き、成分の「開いた側」の数で和を前払いする）

📋 コピーimport sys

MOD = 998244353


def main():
    n, k = map(int, sys.stdin.read().split())
    if n == 1:
        print(1 if k == 0 else 0)
        return
    L = k + 1
    zero = [0] * L
    # dp[e][j]: 長さ L のリスト。値 1..v を置き、連結成分 j 個、端に固定した成分 e 個、
    #           確定した和が s の通り数を dp[e][j][s] に持つ（None は全部 0）
    dp = [[None] * (n + 2) for _ in range(3)]
    dp[0][1] = [1] + [0] * k          # 値 1 を端以外に置く
    dp[1][1] = [2] + [0] * k          # 値 1 を左端か右端に置く

    def add(dst, e, j, row, c):
        # dst[e][j] += c * row
        if c <= 0:
            return
        t = dst[e][j]
        if t is None:
            dst[e][j] = [c * b for b in row]
        else:
            dst[e][j] = [a + c * b for a, b in zip(t, row)]

    for v in range(2, n + 1):
        nd = [[None] * (n + 2) for _ in range(3)]
        jmax = n - v + 1                # 残りの値で併合できる成分数の上限
        for e in range(3):
            for j in range(1, n + 1):
                row = dp[e][j]
                if row is None:
                    continue
                # 値 v-1 と v の間を跨ぐ隣接対 = 成分の開いた側の数 2j - e を和に足す
                c = 2 * j - e
                if c > k:
                    continue
                if c:
                    row = zero[:c] + row[:L - c]
                if j + 1 <= jmax:
                    add(nd, e, j + 1, row, j + 1 - e)        # 新しい成分を端以外のすき間に
                    if e < 2:
                        add(nd, e + 1, j + 1, row, 2 - e)    # 新しい成分を端に
                if j <= jmax:
                    add(nd, e, j, row, 2 * j - e)            # 成分の片側にくっつける
                    if e < 2:
                        add(nd, e + 1, j, row, 2 - e)        # 端側の成分の外側にくっつけ端にする
                if j >= 2 and j - 1 <= jmax:
                    add(nd, e, j - 1, row, j - 1)            # 隣り合う 2 成分をつなぐ
        for e in range(3):
            for j in range(n + 2):
                if nd[e][j] is not None:
                    nd[e][j] = [a % MOD for a in nd[e][j]]
        dp = nd
    row = dp[2][1]
    print(row[k] % MOD if row is not None else 0)


main()