一种较为简单的直接对整体函数插值的解法

求从每个点出发能走的步数之和等同于求每一步合法位置的数量之和。更进一步地，假设每一维的出发坐标均为 $0$，在走了 $i$ 步之后第 $j$ 维经过坐标的最小值为 $l_{i, j}$，最大值为 $r_{i, j}$，那么答案为 $\sum_{i} \prod_{j = 1}^k [w_j - (r_{i, j} - l_{i, j})]$。
将每 $n$ 步视为一个周期，那么从第二个周期开始，每个周期内 $l_{i, j}, r_{i, j}$ 的变化情况是相同的。第一个周期的答案可以暴力计算，第 $x(x \geq 2)$ 个周期的答案可以表示为一个关于 $x$ 的函数 $f(x) = \sum_{i = 1}^n \prod_{j = 1}^k[w_j - (r_{n, j} - l_{n, j}) - c_{i, j} - (x - 2) c_{n, j}]$，其中 $c_{i, j}$ 表示从第二个周期开始的每个周期内，走了 $i$ 步之后第 $j$ 维坐标的 $r_{*, j} - l_{*, j}$（$*$ 即对应总步数）会增加多少。注意到整个 $f(x)$ 是一个关于 $x$ 的 $k$ 次多项式，因此我们计算答案所需要的 $f(x)$ 的前缀和则可以表示为一个 $k + 1$ 次多项式，当 $x$ 较大时，使用拉格朗日插值即可求得结果。