本文主要讨论形式幂级数在解决数学问题以及算法竞赛问题的思维，因此并不会涉及形式幂级数运算的编程实现。
例题引入
问题1
有 $3$ 个集合 $A=\{2,3\}, B=\{2,4\},C=\{3,5,7\}$ ，现在要求从三个集合中各选择恰好一个元素 $a,b,c$ 使得 $a+b+c=n$ ，询问有几种方案？
题解1
构造多项式 $f(x)=(x^2+x^3)(x^2+x^4)(x^3+x^5+x^7)$ ，那么 $x^n$ 这一项的系数就是本题的答案。
由于接下来 $x^n$ 这一项的系数这一概念经常出现，我们采用符号 $[x^n]f(x)$ 来指代这一概念。
因此，本题的答案可以简记作 $[x^n](x^2+x^3)(x^2+x^4)(x^3+x^5+x^7)$ 。
问题一引出的两种思路
基于分配律的解释
一般地，对于形如 $(a_0+a_1+a_2+\cdots)(b_0+b_1+b_2+\cdots)(c_0+c_1+c_2+\cdots)$ 这类连乘式的计算，我们都可以从分配律的角度进行思考，例如在问题 $1$ 这个样例中：
- 在 $x^2$ 和 $x^3$ 中选择一个。
- 在 $x^2$ 和 $x^4$ 中选择一个。
- 在 $x^3,x^5$ 和 $x^7$ 中选择一个。
- 将上方所有的选择情况累加起来（根据乘法原理一共 $2\times 2\times 3=12$ 种）。
因此，对于 $[x^n](x^2+x^3)(x^2+x^4)(x^3+x^5+x^7)$ 而言，当所有选项中不同的 $x^a,x^b,x^c$ 方案累加在一起后，得到的 $x^{a+b+c}=x^n$ 的系数就是答案。
基于状态转移的解释
个人认为这个思考角度可以类比动态规划的状态转移思路。
同样以问题一为例：
- 一开始我们什么都没有，因此状态为 $1$ 。
- 从集合 $A$ 中选择元素，因此状态变为 $1\times(x^2+x^3)$ 。
- 从集合 $B$ 中选择元素，有以下 $2$ 种不同的选择：
- 选择了 $x^2$ ，那么状态变为 $(x^2+x^3)x^2$ ；
- 选择了 $x^4$ ，那么状态变为 $(x^2+x^3)x^4$ ；
- 将这两种转移合并，$(x^2+x^3)(x^2+x^4)$ 。
第三步的状态转移实际上相当于：现在有「+2的选择分支」和「+4的选择分支」，不论选择哪个分支，我们都可以用乘法代替这一选择（这利用了指数的特征，将所有元素+2相当于 $\times x^2$）。而这两种不同的选择所导致的不同结果在当前这一层转移中的地位又是等价的，因此我们可以把所有情况再次累加到一起，就能表示出当前所有的状态了。
- 从集合 $C$ 中选择元素，有以下 $3$ 中不同的选择：
- 选择了 $x^3$ ，那么状态变为 $(x^2+x^3)(x^2+x^4)x^3$ ；
- 选择了 $x^5$ ，那么状态变为 $(x^2+x^3)(x^2+x^4)x^5$ ；
- 选择了 $x^7$ ，那么状态变为 $(x^2+x^3)(x^2+x^4)x^7$ ；
- 将这三种转移合并，$(x^2+x^3)(x^2+x^4)(x^3+x^5+x^7)$ 。
虽然目前为止只解决了一个问题，但是我们已经有了一个利用多项式方法解决数学问题的思路。继续思考以下问题：
问题2
有 $2$ 个苹果，$3$ 个橘子，$4$ 个葡萄。从中买恰好 $n$ 个水果的方法有几种？
题解2
$[x^n](1+x+x^2)(1+x+x^2+x^3)(1+x+x^2+x^3+x^4)$
本问题比较简单，唯一的一个问题就是：由于我们可以选择不买某种水果，因此在构造多项式时需要加入一个等价于什么都不做的选项，也就是系数 $1$ （因为 $1$ 在多项式中等价于 $x^0$ ）。
问题3
有无限数量的苹果，橘子，葡萄。从中买恰好 $3$ 个水果的方法有几种？
题解3
构造多项式 $f(x)=(1+x+x^2+x^3+\cdots+x^n)^3=(\sum_{i=0}^{\infty}x^i)^3$ ，本题答案就是 $[x^3]f(x)$ 。
或者换一个角度，由于在本问题中三种不同水果的地位是完全等价的，因此可以有 $f=\sum_{i=0}^{\infty}x^i$ ，本题答案为 $[x^3]f^3$ 。
因为对某种水果的选择没有限制，因此出现了无穷级数，这就是本文的主角“形式幂级数”。
练习题
计数时的应用
问题4
给定集合 $A=\{a_1,a_2,\ldots,a_k\}$ ，询问有几对 $(i,j)$ 满足 $n=a_i+a_j$ ？
题解4
构造多项式 $f=x^{a_1}+x^{a_2}+\cdots+x^{a_k}$ ，答案就是 $[x^n]f^2$ 。
一些关联问题：Yukicoder723 2つの数の和，AtCoder149E Handshake。
问题5
有 $N$ 个方格依次排列在一条直线上，初始位置在第一个方格。每一轮中我们可以从第 $x$ 个方格跳跃到第 $x+2$ 或者 $x+3$ 个方格，询问恰好 $n$ 轮后到达终点（第 $N$ 个方格）的方案数？
题解5
$[x^{N-1}](x^2+x^3)^n$
问题6
有 $N$ 个方格依次排列在一条直线上，初始位置在第一个方格。每一轮中我们可以从第 $x$ 个方格跳跃到第 $x+2$ 或者 $x+3$ 个方格，询问任意轮后到达终点（第 $N$ 个方格）的方案数？
题解6
$\sum_{n=0}^{\infty}[x^{N-1}](x^2+x^3)^n$
问题7
有 $1$ 元硬币，$5$ 元硬币和 $10$ 元硬币无限多个，请问从中取任意多个硬币恰好构成 $n$ 元的方案数？
题解7
构造 $f_1=\sum_{n=0}^{\infty}x^n,f_5=\sum_{n=0}^{\infty}x^{5n},f_{10}=\sum_{n=0}^{\infty}x^{5n}$ ，
则答案为 $[x^n]f_1f_{5}f_{10}$ 。
这题本质上和问题 $3$ 是等价的。
问题8
现有重量 $w_1$ 的物品，重量 $w_2$ 的物品，重量 $w_3$ 的物品，……，重量 $w_k$ 的物品各一件。询问在一个最大载重量为 $W$ 的背包中有几种不同的物品装入方案（对于每种物品都可以选择放入或者不放入）
题解8
$\sum_{n=0}^{W}[x^n](1+x^{w_1})(1+x^{w_2})(1+x^{w_3})\cdots(1+x^{w_k})$ ，
也可以简写成 $\sum_{n=0}^{W}[x^n]\prod_{i=1}^k(1+x^{w_i})$ 。
很明显，这就是 $01$ 背包问题。
问题9
$a_1+a_2+\cdots+a_8=6N$ ，询问满足 $0\leq a_i\leq N$ 的整数元组 $(a_1,a_2,\cdots,a_8)$ 的数量？
题解9
$[x^{6N}](1+x+x^2+\cdots+x^N)^8$
本题出处：Yukicoder287 場合の数，AC代码
问题10
已知 $A,B,C$ 都是素数，且 $A,B,C\leq N$ ，询问使得 $A+B+C$ 仍然是质数的三元组 $(A,B,C)$ 的数量？
题解10
显然，我们可以先预处理出 $[1,x]$ 区间中所有素数的集合，假设为 $P_x$ 。构造 $f=\sum_{p\in P_{N}}x^p$ ，答案就是 $\sum_{p\in P_{3N}}[x^p]f^3$ 。
出处：Yukicoder732 3PrimeCounting，AC代码 。
注意Yukicoder这题是问题10的加强版，他额外要求三元组 $(a,b,c)$ 满足 $a<b<c$ ，因此我们还需要进行一个容斥。观察后易知若 $a+b+c$ 为素数，则只有两种情况：$a<b<c$ 或 $a=b<c$ ，简单容斥一下就可以得出答案了。
问题11
询问将 $N$ 表示为正整数之和的方案数？先后顺序不同也视作不同方案，比如 $3=1+2$ 和 $3=2+1$ 视作两种不同方案。
题解11
构造 $f=\sum_{i=1}^{\infty}x^i$ ，
则答案为 $[x^N]\sum_{i=0}^{\infty}f^i$ 。
这道题还可以通过递推或者组合意义直接给出答案：$2^{N-1}$ 。
问题12
询问将 $N$ 表示为正整数之和的方案数？先后顺序不同视作相同方案，比如 $3=1+2$ 和 $3=2+1$ 视作同一种方案。
题解12
构造 $f_k=\sum_{i=0}^{\infty}x^{ki}$ ，
答案为 $[x^N]\prod_{k=1}^{\infty} f_k$
由于顺序不同也视作相同方案，因此我们只需要枚举取了 $a_1$ 个 $1$ ，$a_2$ 个 $2$ ，……，$a_n$ 个 $n$ 。
问题13
询问将 $N$ 表示为互不相同正整数之和的方案数？
题解13
构造 $f_k=1+x^k$ ，
答案为 $[x^N]\prod_{k=1}^{\infty} f_k$
这其实就是个01背包。
问题14
已知 $N,M$ 是正整数，大小为 $N$ 的数列 $A$ 中的每一项 $A_i$ 在 $[1,M]$ 的范围内且 $A_N=M$ 。并且，对于任意的 $i\in [1,N-1]$ 均成立有：$3\leq A_{i+1}-A_{i} \leq 5$ 。询问合法数列 $A_N$ 的数量？
题解14
构造 $f=\sum_{i=1}^{M}x^i, g=x^3+x^4+x^5$ ，
答案为 $[x^M]fg^{N-1}$ 。
可以从状态转移的角度思考这个方法的合理性，因为首项 $A_1$ 不确定，因此起始状态可能是 $1,2,\ldots,M$ 中的任意一项。然后每个 $A_{i+1}$ 都比 $A_{i}$ 大 $3,4$ 或者 $5$ ，即乘上一个多项式 $g$ 。
问题15
已知 $N,M$ 是正整数，大小为 $N$ 的数列 $A$ 中的每一项 $A_i$ 在 $[1,M]$ 的范围内且 $A_N \lt M$。并且，对于任意的 $i\in [1,N-1]$ 均成立有：$3\leq A_{i+1}-A_{i} \leq 5$ 。询问合法数列 $A_N$ 的数量？
题解15
构造 $f=\sum_{i=1}^{M}x^i, g=x^3+x^4+x^5$ ，
答案为 $\sum_{i=1}^{M-1} [x^i]fg^{N-1}$ 。
或者，也可以表示为 $[x^M]f\cdot g^{N-1}\cdot f$ 。
上方解答中的第一个做法非常普通，应该不难想到。重点是第二个做法相对比较巧妙，因为 $A_N \lt M$ ，所以我们不妨补上一项 $A_{N+1}=M$ ，那么最后一步可以从任意的正数转移过来。
概率论中的应用
问题16
掷出一个均匀的骰子 $100$ 次，求正面朝上的数字之和为 $N$ 的概率。
题解16
构造 $f=\frac{1}{6}(x+x^2+\cdots + x^6)$ ，
答案为 $[x^N]f^{100}$ 。
用系数表示概率，我们就可以用形式幂级数解决概率论相关问题。
问题17
实数 $p,q$ 满足 $p+q=1$ 。一开始我们位于一维数轴的原点，现在我们会将一枚硬币掷出 $100$ 次，如果正面朝上就向正方向前进一步，否则就向反方向前进一步，这枚硬币正面朝上的概率为 $p$ ，反面朝上的概率为 $q$ ，询问最终位于 $x=n$ 这一位置的概率？
题解17
构造 $f=px^{1}+qx^{-1}$ ，
答案为 $[x^n]f^{100}$ 。
这题的背景就是一维平面上的随机游走问题。
本题中第一次出现了幂次为负数的项，这类多项式被称为Laurent多项式，不过在思维层面和一般常见的多项式几乎没什么区别，但是在编程实现时我们不能采用负数的幂次，因此常用以下方案实现：
问题17的答案是 $[x^n](px+qx^{-1})^{100}$ ，我们可以做一个简单的偏移将其转化为 $[x^{n+100}]x^{100}(px+qx^{-1})^{100}$ ，更进一步地：$[x^{n+100}](px^2+q)^{100}$ 。
带系数的转移
问题18
将一个正整数 $N$ 划分为一堆正整数 $N=a_1+a_2+\cdots + a_k$ （定义同问题11），然后我们定义某个划分的“美感”是 $\prod_{i=1}^{k}a_i^2$ ，询问所有划分的“美感”之和？
题解18
构造 $f=\sum_{k=1}^{\infty}k^2x^k=x+4x^2+9x^3+16x^4+\cdots$ ，
答案为 $[x^N]\sum_{i=0}^n f^{i}$ 。
对于本题，我们相当于在转移时给每一项都添加了系数，这个系数就是本题中每一项的“美感”定义。
高维的状态转移
高维的状态转移需要多元多项式解决，因此直接利用代码实现是比较困难的，但是这对于思维的帮助较大，并且有时候我们可以进行一些数学上的变换使得我们可以处理这类转移。
问题19
商品 $A$ 售价 $3$ 元，重量 $4$ 克；商品 $B$ 售价 $5$ 元，重量 $6$ 克。每件商品都至多购买 $2$ 个，询问恰好花费 $n$ 元 $m$ 克购买商品的方案数。
题解19
构造 $f=1+x^3y^4+x^6y^8, g=1+x^5y^6+x^{10}y^{12}$ ，
答案为 $[x^ny^m]fg$ 。
因为每件商品都有两个属性（售价，重量），因此我们可以用二元多项式维护状态的转移。
问题20
有 $1$ 元硬币，$5$ 元硬币和 $10$ 元硬币无限多个，请问从中取恰好 $n$ 个硬币构成 $m$ 元的方案数？
题解20
构造 $f_1=\sum_{i=0}^{\infty}x^iy^i, f_5=\sum_{i=0}^{\infty}x^{5i}y^{i}, f_{10}=\sum_{i=0}^{\infty}x^{10i}y^i$ ，
答案为 $[x^my^n]f_1f_5f_{10}$ 。
问题21
在二维平面上随机游走，一开始你位于坐标原点，每一秒你都等概率地向上下左右四个方向移动一个单位，询问 $T$ 秒后恰好走到点 $(a,b)$ 的概率？
题解21
构造 $f=\frac{1}{4}(x+x^{-1}+y+y^{-1})$ ，
答案为 $[x^ay^b]f^T$ 。
问题22
有三个变量 $X,Y,Z$ ，初始都是 $0$ ，现在你可以对这些变量执行以下两种操作：1. 选择一个变量 $+1$ 或 $-1$ ，2. 将所有变量 $+1$ 或 $-1$ 。询问 $N$ 回合后变成 $X=p,Y=q,Z=r$ 的情况数？
题解22
构造 $f=x+x^{-1}+y+y^{-1}+z+z^{-1}+xyz+(xyz)^{-1}$ ，
答案为 $[x^py^qz^r]f^N$ 。
来源：Kyoto University Programming Contest 2019 K – One or All，AC代码 。题解请参考下一篇文章。
问题23
在三维空间中初始位于原点，每一秒都会进行一次移动，每一次移动都可以选择一个非负整数的三元组 $(a,b,c)\neq (0,0,0)$ ，然后从 $(x,y,z)$ 点移动至 $(x+a,y+b,z+c)$ 点。询问到达 $(X,Y,Z)$ 的不同方案数
题解23
构造 $f_x=1+x+x^2+\cdots,f_y=1+y+y^2+\cdots,f_z=1+z+z^2+\cdots,f=f_xf_yf_z-1$ ，
答案为 $\sum_{i=0}^{\infty}[x^Xy^Yz^Z]f^i$ 。
来源：Yukicoder940 ワープ ε=ε=ε=ε=ε=│;p>д＜│
问题24
在三维空间中初始位于原点，每一秒都会等概率地移动至相邻的六个格点之一，求 $T$ 秒后到达点 $(a,b,c)$ 且满足 $3a+4b+5c=n$ 的概率？
题解24
构造 $f=\frac{1}{6}(x+x^{-1}+y+y^{-1}+z+z^{-1})$ ，答案为 $\sum_{n=3a+4b+5c}[x^ay^bz^c]f^T$ 。
但这并不是最优解，我们可以对该式换元：$x=t^3,y=t^4,z=t^5$ ，那么 $x^ay^bz^c=t^{3a+4b+5c}$ ，那么本题就转化为了 $[t^n]\frac{1}{6}(t^3+t^{-3}+t^4+t^{-4}+t^5+t^{-5})^T$
来源：Yukicoder612 Move on grid