一道不太 GF 的题，用 GF 大力推导

· · 个人记录

原题链接：3rd UCup Stage 34: C

简要题意：

对于 T 组数据，给定 n，分别求出

[x^n]\prod_{i=0}^\infty \frac{1}{1-2^i x^{2^i}}

答案对 998244353 取模。

有位 不愿透露姓名的同学 问我：「这个题的官方做法是数位 DP，有没有大力 GF 的做法呢？」

我回复：「有的兄弟，有的。」然后半小时胡了个假做法就跑路了。（为了所谓 GF 大蛇的颜面，原假做法在剪贴板上已经删掉了。除非洛谷有存档能还原。）

之后回来看私信才发现假完了，以下是正确做法及思路。

如果你尝试展开这个幂级数的一些项，可以发现 2n 和 2n+1 位置的答案相同，所以我们可以直接把 n 整除 2 后再继续计算。

那这个过程还能不能继续下去呢？如果你学过 Bostan-Mori 算法，那就能发现这是可以套用过去的。

考虑已经给定次数较低的多项式 P(x),Q(x) 和常数 k，要求解：

\begin{aligned} &[x^n] \frac{P(x)}{Q(x)} \prod_{i=0}^\infty \frac{1}{1-2^{i+k}x^{2^i}} \\ &=[x^n] \frac{P(x)}{Q(x) (1-2^k x)} \prod_{i=1}^\infty \frac{1}{1-2^{i+k}x^{2^i}} \\ &= [x^n] \frac{P(x)Q(-x)(1+2^kx)}{Q(x)Q(-x)(1-4^k x^2)}\prod_{i=0}^\infty \frac{1}{1-2^{i+k+1}x^{2^{i+1}}}\end{aligned}

然后设 V(x^2)=Q(x)Q(-x)(1-4^k x^2)，以及将 P(x)Q(-x)(1+2^k x) 按照奇偶分类为 U_0(x^2)+xU_1(x^2)，我们就只需要依次执行以下操作：

直到 n=0，即可返回答案为 P(0)。

考虑分析一下时间复杂度，每次 \deg Q 都会增加 1，如果不使用 FFT，单次计算复杂度为 \Theta(\log^3 n)。

所以我们还需要做点预处理，考虑到上述过程只要迭代的次数相同，那么得到的 Q(x) 都是一样的，可以尝试预处理初始的几次迭代。

那么接下来要怎么操作，相信读者也容易想到。就算想不到也没关系，可以参考代码实现，时间复杂度为 \Theta(\sqrt n \log^2 n + T \log n)。