自动搬运

查看原文

来自洛谷，原作者为

	x义x “我们要走多远？”“一百万年。”

搬运于2025-08-24 22:34:03，当前版本为作者最后更新于2021-10-12 18:34:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

贺的官方题解

猜猜我官方题解哪里来的？

考虑 $(0,0)\rightarrow(n,-1)$ 且除了最后一步外从未接触 $y=-1$ 的路径们，记其生成函数为 $F$。

讨论其第一步，我们有

$$F=x\sum_{i=-1}a_{i}F^{i+1}$$

自然，

$$\boxed{F^{<-1>}=\dfrac{x}{\sum_{i=-1}a_ix^{i+1}}}$$

考虑所希望的 $(0,0)\rightarrow (n,0)$ 且除了起点和终点从未接触过 $y=0$ 的路径，故技重施，有

$$ans=x\sum_{i=0}a_iF^i$$

而接触 $y=0$ 恰好 $m+1$ 次的就是

$$\boxed{ans=\left(x\sum_{i=0}a_iF^i\right)^m}$$

使用拉格朗日反演：

$$\begin{aligned} &[x^{n-m}]\left(\sum_{i=0}a_iF^i\right)^m\\=&\dfrac{[x^{n-m-1}]}{n-m}\cdot m\left(\sum_{i=1}ia_ix^{i-1}\right)\left(\sum_{i=0}a_ix^{i}\right)^{m-1}\cdot\left(\sum_{i=-1}a_ix^{i+1}\right)^{n-m} \end{aligned} $$

于是问题变为求一个稀疏多项式的高次幂的前较低项系数。有 ODE：

$$f(f^m)'=mf'f^m$$

也就得到了一个 $f^m$ 的整式递推。