自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 23:15:57，当前版本为作者最后更新于2025-05-15 10:20:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

来一个和官方题解不一样的做法，代码暂时没写，但经过暴力做法验证。

---

一：去除 $m$ 的限制

如果没有「每 $m$ 天必须清空锅」的限制，那么原问题就是比较经典的限制范围的格路计数问题。所以来考虑怎么把问题化简一下。

利用符号化计数的思想，考虑所有「没有清空锅的极长连续段」，那么所有 $n$ 天的情况就是由若干连续段拼接成的。

具体来说，设 $f_i$ 为 $i=n$ 时原问题的答案，$g_i \ (1 \leq i \leq m)$ 为「长度为 $i$ 的极长连续段」的答案，则有：

$$F(x) = \frac{1}{1-G(x)}$$

其中 $F(x)$ 和 $G(x)$ 分别为 $\{ f_i \}$ 和 $\{ g_i \}$ 的生成函数。

我们知道，在 $i \leq m$ 的时候，原问题的答案等同于「不必须清空锅」情况的答案，并设其为 $\hat f_i \ (0 \leq i \leq m)$，所以我们有

$$F(x) \equiv \hat F(x) \pmod {x^{m+1}}$$

这样就能直接求出 $G(x)$：

$$G(x) \equiv 1-\hat F(x)^{-1} \pmod{x^{m+1}}$$

由于 $G(x)$ 本身就是个 $m$ 次多项式，对 $x^{m+1}$ 取模并不影响计算的结果。

这样在求出 $\hat F(x) \bmod x^{m+1}$ 后，就只需要用两次多项式求逆即可得到答案。

---

二：朴素地算 $\hat F(x)$

因为算出 $\hat F(x)$ 的后续工作都很简单，下文中 $G(x)$ 及 $g_i$ 的定义将与上文不同。

从 $(0,0)$ 出发，每一步有 $a_d$ 的概率坐标变化量为 $(1,d)$，不能越过 $y=0$ 且越过 $y=k$ 时会 $y$ 坐标强制移动到 $k$。设 $g_{i,j}$ 为上述问题中走 $i$ 步后到 $(i,j)$ 位置的概率。

显然有 $\hat f_i = \sum_j g_{i,j}$，而根据问题定义容易写出 $g_{i,j}$ 的 DP：

$$g_{i+1,\min(j+d,k)} \leftarrow g_{i,j} a_d \ \ (j+d \geq 0) $$

---

三：麻烦地算 $\hat F(x)$

设 $G_j(x)=\sum_i g_{i,j} x^i$，那么根据递推式我们可以得到一个关于 $G_j(x)$ 的 $k+1$ 元线性方程组。具体而言，对 $0 \leq j < k$ 都有：

$$G_j(x)= [j=0]+x\sum_{i=l}^r a_i G_{j-i}(x)$$

而对于 $j=k$ 的情况，会多一部分越过 $y=k$ 强制到 $k$ 而产生的贡献（称其为终点方程），不过形式上还是很相似的。

如此就得到了 $k+1$ 条方程，将 $G_0(x)$ 设为一个未定元，由此 $G_j(x)$ 都可以表示为 $A_j(x)G_0(x)+B_j(x)$ 的形式，可以依此递推出来。

最后根据「终点方程」解出 $G_0(x)$，也就解出了所有 $G_j(x)$，最后计算 $\hat F(x)=\sum_j G_j(x)$ 即可。

---

四：更麻烦但更快地算 $\hat F(x)$

显然上述做法的时间复杂度是很大的，但是注意到 $G_j(x) \ (1 \leq j < k)$ 的方程是一个常系数齐次线性递推。根据其通项的性质，我们可以直接判断出 $A_j(x)$ 和 $B_j(x)$ 必然都是微分有限的幂级数。

为什么？这里以 $l=-3,r=3$ 的情况来说明。此时 $G_j(x)$ 的递推式是 $6$ 阶常系数的，要得到其通项需要解一个 $6$ 次的特征方程（不需要真的解出来，在计算中可以代数扩域），其解 $u_1,\cdots,u_6$ 自然也是代数幂级数，假设没有重根。

那么其通项

$$G_j(x) = \sum_{i=1}^6 (U_i(x) G_0(x) +V_i(x)) u_i^j $$

显而易见，代数幂级数复合进微分有限幂级数中，结果仍然微分有限。对于有重根的情况，证明也是类似的。

现在就可以求出 $A_j(x)$（和 $B_j(x)$） 的 ODE 或其系数的整式递推式（用含 $j$ 的表达式以方便对所有 $j$ 求解）：

• 一种方法是 ODE 自动机，这在实现上可能比较复杂，不过有一些现成的模板可以参考。

• 另一种方法是求出前面一些项，然后用高斯消元找出整式递推式。但这种方法需要对多个 $j$ 计算后，将递推式中的每个系数都对 $j$ 做多项式插值。

设 $D=r-l$，可以证明 $A_j(x)$ 存在 $D+O(1)$ 阶、$D+O(1)$ 次的整式递推，而递推系数中 $j$ 的最高次数也是 $D+O(1)$ 的。

得到了 $A_j(x)$ 的 ODE 后，求出 $\sum_j A_j(x)$ 的 ODE 就很简单了。直接对所有 $j$ 把 $A_j(x)$ 的 ODE 中的系数全部加起来即可。

ODE 自动机的复杂度不太会分析，但是高斯消元法求出整式递推的复杂度是 $\Theta(D \times (D^2)^3)=\Theta(D^7)$ 的（要做 $D$ 次才能插值，而每次需要求出 $\Theta(D^2)$ 项解一个 $\Theta(D^2)$ 元方程组，再算上消元本身的三次方时间）。

这样就可以做到 $\Theta(D^7+ n D^2\log n)$。