其实并不用强行拆式子拆出「自然数整数次幂的前缀和」形式再插值。

以下这段粘自我的 blog：

求从每个点出发能走的步数之和等同于求每一步合法位置的数量之和。更进一步地，假设每一维的出发坐标均为 $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$ 较大时，使用拉格朗日插值即可求得结果。

然而，即使用插值不是求 $f(x)$ 的前缀和，而是直接求每个 $f(x)$，也能够通过官方数据，因为后面的测试点尽管 $w_i$ 很大但 $\frac{w_i}{n}$ 较小。然后我在 UOJ 上自己把自己叉了。