营业日志 2020.7.4 新瓶旧酒

今天 cuizhuyefei 哥哥给了这么一个问题： $$ b_i = \sum_j \binom{2i-j}{i-j} a_j $$ 的求算。 djq_cpp 一语道破，对于 $a_0$ 的贡献是 $\binom {2i}{i}$，这容易让我们联想到其生成函数是二次根式 $\frac{1}{\sqrt{1-4z}}$。 因此启发我们将变换写作 $$ \sum_n b_n z^n = \sum_k a_k \left(\sum_n \binom {2n-k}{n-k} z^n \right) $$ 我们将考虑记 $Q_k(z) = \sum_n \binom {2n-k}{n-k} z^n = z^k \, _2F_1\left(\frac{k+1}{2},\frac{k+2}{2};k+1;4 z\right)$。 容易想到通过 $\binom nm = \binom{n+1}{m+1} - \binom{n}{m+1}$ 来建立 $Q_k$ 之间的递推联系。 $$ \begin{aligned} Q_k(z) &= \sum_n \binom {2n-k}{n-k} z^n \\ &= \sum_n \left(\binom {2n-k+1}{n-k+1} - \binom {2n-k}{n-k+1} \right) z^n\\ &= \sum_n \left(\binom {2n-(k-1)}{n-(k-1)} - \binom {2(n-1)-(k-2)}{(n-1)-(k-2)} \right) z^n\\ &= \sum_n \binom {2n-(k-1)}{n-(k-1)} z^n - z \sum_n \binom {2(n-1)-(k-2)}{(n-1)-(k-2)} z^{n-1}\\ &= Q_{k-1}(z) - zQ_{k-2}(z) \end{aligned} $$ 而 $Q_0 = \frac 1{\sqrt{1-4z}}$ 已知（广义二项式），$\binom {2n-1}{n-1} = \frac{\binom{2n}{n} - [n=0]}2$ 进一步可得 $Q_1 = \frac{1-\sqrt{1-4z}}{2\sqrt{1-4z}}$。这样这个线性递推的要素就齐全了。然后你算出来发现它就是 $$ Q_k(z) = \frac{\left(\frac{1-\sqrt{1-4z}}{2}\right)^k}{\sqrt {1-4z}}\\ $$ [换个马甲我就不认识你了……](https://www.luogu.com.cn/blog/EntropyIncreaser/ying-ye-ri-zhi-202059-post) 因此 $B(z) = \frac{A\left(\frac{1-\sqrt{1-4z}}{2}\right)}{\sqrt{1-4z}}$，接下来如何计算就比较简单了，首先是 $A(\frac{1-t}2)$ 很好做，然后复合 $\sqrt{1-4z}$ 只需要奇偶部分分别伺候，总共就是若干次 $\Theta(n\log n)$ 的变换了。