自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 23:10:29，当前版本为作者最后更新于2025-02-25 10:36:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

update：修了点笔误。

---

Q：主播主播，你的问题转化 + 符号化做法确实很强，但还是太吃操作了。有没有更加简单效果又好的做法推荐一下呢？

A：有的兄弟，有的！

---

目前主要有的线性做法都要做一下问题模型的转化，可能并不是很容易操作（相比较于 $\Theta(n^3)$ 复杂度的做法来说）。

稍微转化一下可以得到 $\Theta(n^3)$ 计算的式子长这样：

$$\frac{1}{4^n}\sum_{i+j+k+t=n} (-1)^{j+k}\binom{n}{i,j,k,t}2^{2i+2j+k}\binom{k+t}{k}k! (j+2t)! $$

一眼看过去，这种多重的、无交叉项（各层和式指标之间乘积）的超几何式，就应该是整式递推的嘛！怎么可能不是整式递推？有道理吗？

好吧，这个一般化的结论我也没有证明过。但对于此题来说，使用上式暴力算出前几项，然后使用高斯消元找出整式递推式即可。

不过针对这题的详细推导，我们还是有的。把 $t$ 单独提出来枚举，答案为

$$\frac{1}{4^n}\sum_{t=0}^n \binom nt \frac{1}{t!}\sum_{i+j+k=n-t}(-1)^{j+k}\binom{n-t}{i,j,k}2^{2i+2j+k}(k+t)!(j+2t)! $$

然后我们只关注内层和式，卷积的形式就很明显了，其为

$$(n-t)![z^{n-t}]\left( \sum_{i=0}^\infty \frac{4^i}{i!}z^i\right)\left( \sum_{j=0}^\infty \frac{(-4)^j}{j!}(j+2t)!z^j\right)\left( \sum_{k=0}^\infty \frac{(-2)^k}{k!}(k+t)!z^k\right) $$

这三坨的的封闭形式都很容易求，分别是

$$\text e^{4z}\ , \frac{(2t)!}{(1+4z)^{2t+1}} \ , \ \frac{t!}{(1+2z)^{t+1}} $$

带回去，答案就是

$$\frac{n!}{4^n}\sum_{t=0}^n \frac{(2t)!}{t!}[z^{n-t}] \frac{\text e^{4z}}{(1+4z)^{2t+1}(1+2z)^{t+1}} $$$$=\frac{n!}{4^n}[z^n] \frac{\text e^{4z}}{(1+4z)(1+2z)}\sum_{t=0}^\infty \frac{(2t)!}{t!} \left( \frac{z}{(1+4z)^{2}(1+2z)}\right)^t $$

如此我们通过简单的推导，也得到了转化题意后得到的 GF，殊途同归。最后自然还是要求「微分有限幂级数」复合「代数幂级数」（此处为有理分式）的 ODE，这个都讲过很多，就不赘述了。