Grafy：转化做法还是太吃操作了

· · 题解

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，这个都讲过很多，就不赘述了。