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

简要题意：

对于 $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)

，我们就只需要依次执行以下操作：

$k \leftarrow k+1$
$P(x) \leftarrow \begin{cases} U_0(x) \ , \ [2 \mid n] \\ U_1(x) \ , \ \text{otherwise}\end{cases}$
$Q(x) \leftarrow V(x)$
$n \leftarrow \lfloor n/2 \rfloor$

直到

n=0

，即可返回答案为

P(0)

。

考虑分析一下时间复杂度，每次

\deg Q

都会增加

1

，如果不使用 FFT，单次计算复杂度为

\Theta(\log^3 n)

。

所以我们还需要做点预处理，考虑到上述过程只要迭代的次数相同，那么得到的

Q(x)

都是一样的，可以尝试预处理初始的几次迭代。

那么接下来要怎么操作，相信读者也容易想到。就算想不到也没关系，可以参考代码实现，时间复杂度为

\Theta(\sqrt n \log^2 n + T \log n)

。

文章操作