Day 170-Q3 — 2026-10-05 | 摩天楼の並べ方（高さが任意の値の挿入 DP。値を小さい順に置き、隣の値との差 × 開いた側の数を前払いして「差の和が L 以下」を数える）

📋 コピーimport sys

MOD = 998244353


def main():
    data = sys.stdin.buffer.read().split()
    n, lim = int(data[0]), int(data[1])
    a = sorted(int(x) for x in data[2:2 + n])
    if n == 1:
        print(1)
        return
    L = lim + 1
    zero = [0] * L
    # dp[e][j][s]: 小さい方から v 個を置き、成分 j 個、端に固定した成分 e 個、前払い済みの和 s の通り数
    dp = [[None] * (n + 2) for _ in range(3)]
    dp[0][1] = [1] + [0] * lim        # 最小の値を端以外に置く
    dp[1][1] = [2] + [0] * lim        # 最小の値を左端か右端に置く

    def add(dst, e, j, row, c):
        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] = [x + c * b for x, b in zip(t, row)]

    for v in range(2, n + 1):           # v 個目の値 a[v-1] を置く
        gap = a[v - 1] - a[v - 2]       # 1 つ前の値との差。開いた側 1 つにつき gap を前払い
        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
                c = (2 * j - e) * gap
                if c > lim:
                    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] = [x % MOD for x in nd[e][j]]
        dp = nd
    row = dp[2][1]
    print(sum(row) % MOD if row is not None else 0)


main()