右复合常数项非零幂级数怎么做？

· · 题解

给定形式幂级数 f(x),g(x)，其中 f(x) 有无限多非零项，而 g(x) 的常数项非零。要提取 f(g(x)) 的系数该怎么做呢？

例题链接

一句话题意：给定 N,A，求出

\lim_{m\to +\infty}[x^N]\prod_{i=1}^m\left( \left( 1-\frac{1}{i^2}\right)+\frac{x}{i^2}\right)^A

可以证明其可以表示为关于 \pi 不超过 N 次的有理系数多项式，求出低于 N 次的系数。

题目中提示到了 \pi，又看到这个无穷乘积，会让我们想到利用这个式子：

\sin x=x\prod_{i=1}^\infty\left( 1-\frac{x^2}{i^2 \pi^2}\right)

理解起来很简单，就是找出 \sin x 的所有零点而已。当然更严谨的证明还需要一些数学分析的知识。现在就可以直接得到原问题是

[x^N]\left( \frac{\sin (\pi\sqrt{1-x})}{\pi\sqrt{1-x}}\right)^A

这个东西不好直接计算，因为 \sin x 展开有无穷多项，而内层复合的东西常数项非零，这导致计算中又会用到无限和。

为了把无限和变为有限和，我们还可以使用 载谭 Binomial Sum 中用到的技巧。设：

g(x)=\left(\frac{\sin (\pi(x+1))}{\pi(x+1)}\right)^A\bmod x^{N+1}=-\pi^{-A}\left(\frac{\sin (\pi x)}{x+1}\right)^A \bmod x^{N+1}

这样就可以求 [x^N]g(\sqrt{1-x}-1) 来得到答案了。由于 g(x) 只有有限项，答案就是：

\sum_{i=0}^N([x^i]g(x))([x^N](\sqrt{1-x}-1)^i)

设 a_i=[x^N](\sqrt{1-x}-1)^i，简写为：

(-1)^A\sum_{i=0}^N a_i\sum_{j=0}^i\pi^{j-A}\left( [x^{i-j}]\frac{1}{(1+x)^A}\right)\left([x^{j}](\sin x)^A\right) =(-1)^A\sum_{j=0}^N\pi^{j-A}[x^j](\sin x)^A\sum_{i=0}^Na_i\left([x^{i-j}]\frac{1}{(1+x)^A}\right)

内层和式是一个典型的差卷积，将数列 a 保留前 n 项后翻转的结果记为 a'，则答案为

(-1)^A\sum_{j=0}^N\pi^{j-A}[x^j](\sin x)^A\sum_{i=0}^Na_{N-i}'\left([x^{i-j}]\frac{1}{(1+x)^A}\right)

这样内层的情况就很明显了，可以表示为 a' 和 (1+x)^{-A} 系数的卷积。而根据 经典方法 可知：

a_i=[x^{N-i}](-2-2x)\left( -\frac{1}{2+x}\right)^{N+1}

最后答案就是

2(-1)^{A+N}\sum_{j=0}^N\pi^{j-A} [x^j](\sin x)^A [x^{N-j}]\left(\left( \frac{1}{2+x}\right)^{N+1} \frac{1}{(1+x)^{A-1}}\right)

后面提取系数的那一块显然微分有限，可以整式递推计算。只有求 (\sin x)^A 的系数时需要用到 FFT。

总时间复杂度 \mathcal O(N \log N)。

从此例题中可以看出，解决这类问题的关键在于：f(x+c) 要容易处理。大多数时候 f(x) 具有封闭形式，计算起来还是很方便的。