「EZEC-10」「Byakkai OI 2021」Estahv 官方题解

· · 题解

令 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)。