自动搬运

查看原文

来自洛谷，原作者为

	Aleph1022 「笑可以天然地飘洒 心是一地草野 唯一的家乡」

搬运于2025-08-24 22:32:28，当前版本为作者最后更新于2021-07-07 16:14:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

令 $C(z) = z(1+C(z))^2$ 也就是卡特兰数去掉常数。
分析一下题目给出的代数结构，显然可以刻画成

$$[z^n] \frac1{1-2C(z)G(C(z))}, \qquad G(z) = \frac{zw(2-zw)}{(1-zw)^2} $$

令

$$F(z) = \frac1{1-2zG(z)} = \frac{1-2zw+z^2w^2}{1-2zw+z^2w^2-4z^2w+2z^3w^2} $$

算法 0 from EI

根据直觉可以发现答案是 D-finite 的。
高斯消元即可。

---

或者，作另类拉格朗日反演可得

$$[z^n] F(C(z)) = [z^n] F(z) (1-z)(1+z)^{2n-1}$$

记 $H(z) = (1-z)(1+z)^{2n-1}$。
接下来有两条路可选。

算法 1

考虑记 $h_k = [z^{n-k}] H(z)$，则所求即

$$\sum\limits_{k\ge0} h_k [z^k] F(z)$$

典型的线性算法。考虑转置原理，变成计算

$$\sum\limits_{k\ge0} h_k [w^k] F(z)$$

换元 $s = zw$，

$$\sum\limits_{k\ge0} h_k z^k [s^k] \frac{(1-s)^2}{1-s(2-s)(1+2z)} $$

记 $f_k = z^k [s^k] \frac{(1-s)^2}{1-s(2-s)(1+2z)}$，则可以写出递推式

$$f_k = (1+2z)(2zf_{k-1}-z^2f_{k-2})+[k=0]-2z[k=1]+z^2[k=2] $$

其转移可写作矩阵，则问题变成若干矩阵的前缀积的带权和，可以利用这里的技术做到 $\Theta(n \log^2 n)$。

然后将以上算法转置即可。
时间复杂度 $\Theta(n \log^2 n)$。

算法 2

作代换 $s=zw$，则

$$[w^n] F(z) = z^n [s^n] \frac{(1-s)^2}{1-2s(1+2z)+s^2(1+2z)} $$

作分式分解，则

$$\frac{(1-s)^2}{1-2s(1+2z)+s^2(1+2z)} = \frac{(1-s)^2}{A(z)-B(z)}\left(\frac{A(z)}{1-sA(z)}-\frac{B(z)}{1-sB(z)}\right) $$

其中 $\begin{cases} A(z)=1+2z+\sqrt{2z(1+2z)} \\ B(z)=1+2z-\sqrt{2z(1+2z)} \end{cases}$。

则考虑

$$[w^k z^n] F(C(z)) = [w^k z^n] F(z) H(z)$$

可以拆成若干个

$$[z^m] \frac{z^kH(z)}{A(z)-B(z)} \left(A^{k+1}(z) - B^{k+1}(z)\right) = 2[z^m] \frac{z^kH(z)}{A(z)-B(z)} A^{k+1}(z),\qquad m\in \mathbb Z $$

为了消除 $\sqrt z$ 项，将 $z$ 代换到 $z^2$ 并整理，可以转化为计算

$$[z^{2m+1}] \frac{Q(z)}{1-tP^2(z)}$$

其中

$$P(z)=z\sqrt{1+2z^2+z\sqrt{2(1+2z^2)}}, Q(z)=\frac{(1-z^2)(1+z^2)^{2n-1}(1+2z^2+z\sqrt{2(1+2z^2)})}{\sqrt{2(1+2z^2)}} $$

再次拉格朗日反演即可：

$$[z^{2m+1}] \frac{Q(z)}{1-tP^2(z)} = \frac1{2m+1}[z^{2m}] \left[\frac{Q\left(P^{\langle -1\rangle}(z)\right)}{1-tP^2(z)}\right]' \left(\frac z{P^{\langle -1\rangle}(z)}\right)^{2m+1} $$

令 $R(z)=Q\left(P^{\langle -1\rangle}(z)\right),S(z)=\left(\frac z{P^{\langle -1\rangle}(z)}\right)^{2m+1}$，则

$$\left[\frac{R(z)}{1-tz^2}\right]' = \frac{R'(z) + tz[2R(z)-zR'(z)]}{[1-tz^2]^2} $$

故

$$\begin{aligned} [t^k z^{2m+1}] \frac{Q(z)}{1-tP^2(z)} &= \frac1{2m+1}[z^{2m}]\left[z^{2k}R'(z)S(z) + 2kz^{2k-1}R(z)S(z)\right] \\ &= \frac1{2m+1}\left[[z^{2(m-k)}]R'(z)S(z) + 2k[z^{2(m-k)+1}]R(z)S(z)\right] \end{aligned} $$

总时间复杂度 $\Theta(n \log n)$。