[R83D] 检查

数据规模：$1 \le n \le 100$，$0 \le K \le 10^4$。

思路

已访问的坐标始终是一段连续区间，当前位置必定是它的端点。 一开始已访问集合是 $[0,0]$，位置 $0$ 就是端点。归纳下去：设当前已访问的连续区间为 $[L,R]$，位置在某个端点上。

• 若朝区间外侧跳，该方向上最近的未访问坐标就是端点外侧紧邻的一格，跳长为 $1$；
• 若朝区间内部的方向跳，途中每一格都已访问，最近的未访问坐标在另一端点的外侧一格，跳长等于区间内坐标的个数。

两种情况落点都会把区间向该侧扩长一格，并且新位置仍是端点，归纳成立。

跳长只取决于是否转向。 第 $i$ 次跳跃前，已访问了 $i$ 个坐标（区间内有 $i$ 个整数），所以：

• 第 $i$ 次与第 $i-1$ 次方向相同（继续朝外）：跳长恰为 $1$；
• 第 $i$ 次与第 $i-1$ 次方向相反（转向）：跨过整个已访问区间，跳长恰为 $i$。

第一次跳跃的两侧都未访问，跳长也是 $1$。于是总长度

$n+\sum_{i=2}^{n}[\text{dir}_i\ne\text{dir}_{i-1}]\cdot(i-1).$

转化为带权子集计数。 记 $S=K-n$，问题变成：在 $1\sim n$ 中选出「转向位置」的集合，使其权和（位置 $i$ 的权为 $i-1$）恰好为 $S$ 的方案数，再乘 $2$（第一步的方向有两种）。而每给定一个转向集合和第一步方向，整个方向序列就唯一确定，所以这个乘法不会重复计数。

集合 $\{1,2,\dots,n-1\}$ 的权和最大为 $\frac{n(n-1)}{2}$，因此 $S<0$ 或 $S>\frac{n(n-1)}{2}$ 时直接输出 $0$。

一维背包。 用 $dp[s]$ 表示处理过部分转向位置后权和为 $s$ 的方案数。第一步贡献两种方向，故初始 $dp[0]=2$；之后对 $i=2,3,\dots,n$ 依次加入权 $w=i-1$ 的物品做 0/1 背包，降序枚举 $s$ 原地更新：

$dp[s]\leftarrow dp[s]+dp[s-w].$

最后答案是 $dp[S]$。注意 $dp$ 存的是「转向集合的方案数乘以第一步方向数」，而乘 $2$ 已在初值里完成，后面不再额外乘。

复杂度

背包容量为 $\frac{n(n-1)}{2}=O(n^2)$，共加入 $n-1$ 个物品，时间 $O(n^3)$（$n=100$ 时约 $5\times10^5$ 次加法），空间 $O(n^2)$。

仓颉实现

import std.env.*
import std.convert.*

main() {
    let MOD: Int64 = 998244353
    let t = getStdIn().readln().getOrThrow().split(" ", removeEmpty: true).map({ p: String => Int64.parse(p) })
    let n = t[0]
    let k = t[1]
    let s = k - n
    let mx = n * (n - 1) / 2
    if (s < 0 || s > mx) {
        println(0)
    } else {
        let dp = Array<Int64>(mx + 1, { _ => 0 })
        dp[0] = 2
        for (i in 2..=n) {
            let w = i - 1
            var x = mx
            while (x >= w) {
                dp[x] = (dp[x] + dp[x - w]) % MOD
                x -= 1
            }
        }
        println(dp[s])
    }
}