营业日志 2020.7.4 新瓶旧酒
Elegia
·
·
个人记录
今天 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}}\\
换个马甲我就不认识你了……
因此 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) 的变换了。