这一章节主要通过各种例题的形式幂级数解法，来演示第一章节中的解题思维（或者说将题目翻译成多项式语言？）如何转化为算法实现。

前置芝士

首先你需要知道的是一些常用的多项式化简方法和多项式基本操作。

二项式定理

等比数列求和

形式幂级数的各种操作

参考文章 多项式的各种操作 。

无穷和式的等比变换

在前一篇文章中，我们已经给出了这个问题的答案，但是这个无穷和式在编程实现中较为困难，因此我们需要对其进行代数变换。

由于 $f=x+x^2+\cdots +x^{\infty}$ ，可以通过等比数列求和的方法得到该式即为 $\frac{1}{1-x}-1=\frac{x}{1-x}$ 。

同时，由于 $g=\sum_{i=0}^{\infty}f^i$ ，因此该式也可以通过等比数列求和变换为 $\frac{1}{1-f}$ ，然后我们再将 $f=\frac{x}{1-x}$ 代入，得出本题的答案为：

再通过麦克劳林展开 $\frac{1}{1-2x}$ ，我们就得到了一个在多项式方法中容易处理的形式：

通过观察该式，实际上我们可以得到答案就是 $2^{N-1}$ （当然也可以暴力FFT计算）。

这一系列变换很好地展先出了形式幂级数的“形式”，我们关注的不是数学意义上的级数敛散性，而是通过形式幂级数的系数和幂次来描述一个问题的状态转移，重点是通过多项式的语言来简化复杂的问题。当然，本题通过组合意义或者递推方法解决更加简单。

问题来源：Educational DP Contest M – Candies，AC代码 。

首先很容易想到，构造多项式 $f_i=1+x+x^2+\cdots + x^{A_i}$ ，答案即为 $[x^M]\prod_{i=1}^Nf_i$ 。但是这个式子直接计算必定TLE，因为在极限情况下需要做100次大小为 $10^5$ 的卷积，这是不能接收的，因此我们还需要进行优化。

利用等比变换，$f_i=\frac{1-x^{A_i}}{1-x}$ ，因此我们求解的答案就变成了：

这个式子的分母可以通过多项式快速幂+多项式求逆在 $O(n\log n)$ 的时间复杂度下求出，但是分子的多项式求解好像还有一定问题。观察一下分子的形式后不难看出：其实分子就是一个01背包，你可以将他看作要么什么都不难（取1），要么全拿（取 $A_i$ ）；因此我们在求出分母的多项式系数后，在这个系数数组上进行01背包转移就能解决本题了。

这个做法虽然有简单问题复杂化的嫌疑（本题可以通过前缀和优化dp的思路很轻松地解出），但是一定程度上也体现出了等比变换在形式幂级数问题中的重要性。

问题来源：ARC028D – 注文の多い高橋商店。

对于多次询问，我们显然可以将所有询问先离线下来，然后存一个前缀卷积和一个后缀卷积，回答时从前往后扫一遍。这个做法最大的问题就是常数巨大，一共需要进行 $6000$ 次任意模FFT！恰好会TLE一点点，当然相信是可以卡常卡过去的，这里挂一个我的80分代码以供参考（可以看到也就T了120ms，真的要优化常数还是可行的）。

因此我们需要考虑更优秀的做法，不妨把目光投向上文不多次询问时的方法，令 $F$ 表示：

那么，对于每次的询问 k c ，我们需要的答案就是 $[x^{M-c}]\frac{F}{f_k}$ ，其中$f_k=1+x+x^2+\cdots+x^{a_k}=\frac{1-x^{a_k+1}}{1-x}$。根据前文的解法，$(1-x)F$ 可以在 $O(N\log N + N^2)$ 的时间内解出；然后 $\frac{(1-x)F}{1-x^{a_k+1}}$ 需要 $2000$ 次任意模数FFT，常数显然降了接近一半，可以通过本题。

需要注意的一点是 $\frac{1}{1-x^{a_k+1}}$ 的展开式就是 $1+x^{a_k+1}+x^{2(a_k+1)}+\cdots $ ，这是可以 $O(N)$ 预处理的，不要去求逆！

AC代码。

问题来源：Yukicoder42 貯金箱の溜息。

这题如果 $M$ 不大（比如 $10^5$ 量级），那我们不妨暴力FFT求解，但是这个 $M$ 的量级高达 $10^{18}$ ，因此我们必然需要对该式进行一些简化。注意到一个等比变换的推广：

因此，本题可以变换为 $[x^M]\frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{50})(1-x^{100})(1-x^{500})}$ ，于是我们求出了本题的闭式，但是仍然难以解决本题的核心问题：如何快速求多项式的第 $K$ 项系数。这个问题涉及有理分式形式的闭式和线性递推数列之间的关系，我们将在下一章节中重点介绍，现在先假装可以快速求解。

因式分解

有时候，我们可以通过因式分解的方法对形式幂级数进行一些变形，以达到我们可以处理的形式。

本题来源：ARC012D – Don’t worry. Be Together ，AC代码。

对 $f$ 进行简单的因式分解：

通过二项式定理，将 $f^T$ 展开为：

由于我们需要的是 $[x^ay^b]f^T$ ，因此我们只需要求出满足 $i+j=a \cap T+i-j=b$ 的二元组 $(i,j)$ 以及他们对应的二项式系数即可解决本题。

不过，本题有一个组合数学角度的巧妙解法，思路来源于 知乎上吕欣的回答 。核心思路是：我们将原本的坐标系旋转 $45^{\circ}$ ，代数角度上相当于点 $(x,y)$ 变成了 $(x+y,y-x)$ 。这么做之后，我们的每一步移动都可以看作是同时在 $x$ 轴方向和 $y$ 轴方向移动了一个单位距离（方向不确定）。

这个变换可以让 $x$ 轴和 $y$ 轴的运动变成两个独立的问题，因此如果我们要从 $(0,0)$ 移动到 $(x^{\prime},y^{\prime})$ ，可行的移动方案数就是：

本题来源：Kyoto University Programming Contest 2019 K – One or All，AC代码 。题意和本题几乎是一样的，只不过多了一个参数 $M$ ，本题中的所有操作在本题中均在模 $M$ 意义下进行，也就是说 $X,Y,Z\in [0,M-1]$ 。

这是一个比较困难的题目，需要一些高妙的数学变换。根据上方题解的分析，本题可以通过多项式表示为 $[x^py^qz^r](x+x^{-1}+y+y^{-1}+z+z^{-1}+xyz+(xyz)^{-1})^n$ ，方便起见，我们先不考虑模 $M$ 意义下。

多项式 $x+x^{-1}+y+y^{-1}+z+z^{-1}+xyz+(xyz)^{-1}$ 显然可以通过提取因子转变为 $\frac{1}{xyz}(1+xy)(1+yz)(1+zx)$ ，这个形式非常漂亮，因为他可以看作是两个部分：$(xyz)^{-1}$ 和轮换式 $(1+xy)(1+yz)(1+zx)$ ，而轮换式在编程时可以看作完全相同的结构处理。

由于是轮换式，我们只需要讨论其中一个式子，这里我们以 $1+xy$ 为例：在模 $M$ 意义下，根据二项式定理可以得到 $(1+xy)^N$ 的展开式为：

通过上方的公式，我们可以将模 $M$ 意义下的 $(1+xy)^N$ 改写为系数表达式：$(1+xy)^N=\sum_{i=0}^{M-1}a_i(xy)^i$ 。然后我们回到原式 $\frac{1}{(xyz)^N}(1+xy)^N(1+yz)^N(1+zx)^N$ 中，不妨改写为：

由于我们所求的结果是在模 $M$ 意义下 $x^py^qz^r$ 的系数，因此可以通过枚举 $i$ 并 $O(1)$ 地推出 $j,k$ ，然后判断三元组 $(i,j,k)$ 的合法性统计答案。根据上文的推导，我们知道 $(xy)^i(yz)^j(zx)^k(xyz)^{-N}\equiv x^py^qz^r \pmod{M}$ ，因此如果我们枚举 $i$ ，就有

最后，如果 $(j+k-N)\equiv q\pmod{M}$ ，则三元组 $(i,j,k)$ 符合要求，将 $a_ia_ja_k$ 加入答案。整体的时间复杂度是 $O(N)$ 的。

尽管我们完全没有用到形式幂级数相关的运算，但是本题的核心思路完全是通过多元多项式的数学变换实现的。

问题来源：ABC169F – Knapsack for All Subsets，AC代码 。

瞬间看出结论好像有些困难，那么我们观察一下样例 $A=\{2,2,4\}$ ，构造多项式 $f_1=1+x^2,f_2=1+x^2,f_3=1+x^4$ ，本例的答案为：

这又是一个轮换式，显然可以因式分解为 $[x^S] (1+f_1)(1+f_2)(1+f_3)$ ，而且这个特例可以直接推广到本题的结论：

由于本题中 $N,M,A_i\leq 3000$ ，所以暴力FFT $O(N^2\log N)$ 就可以通过了。

问题来源：ABC159F – Knapsack for All Segments，AC代码 。

显然跟上面那道题是同一个系列的问题，因此我们也先从样例 $A=\{2,2,4\}$ 开始探索，先构造 $f_1=1+x^2,f_2=1+x^2,f_3=1+x^4$ ，本例的答案为：

由于本题多了一个连续区间的设定，我们无法直接因式分解成一个可行的计算公式，但是观察一下上式结构，其实我们可以构造一个递推式：

因此有 $F_{i+1}=(F_i+1)f_{i+1}$ ，于是我们又可以 $O(N^2\log N)$ 暴力草过去了。。。