形式幂级数1-计数问题的多项式视角#

$n$ 次项系数#

对于例1，设多项式 $f=(x^{2}+x^{3})(x^{2}+x^{4})(x^{3}+x^{5}+x^{7})$，则 $[x^n]f$ 表示 $f$ 中 $x^{n}$ 的系数，这个符号将在后文中高频出现，不再赘述。

基于分配律的解释#

一般来说，计算 $(a_{1}+a_{2}+\cdots)(b_{1}+b_{2}+\cdots)(c_{1}+c_{2}+\cdots)$ 这样的乘积时，结果就是把所有形如 $a_{i}b_{j}c_{k}$ 的乘积各加一次。本题中：

• 选择 $x^{2}$ 或 $x^{3}$
• 选择 $x^{2}$ 或 $x^{4}$
• 选择 $x^{3}$、$x^{5}$ 或 $x^{7}$
• 把选到的项的乘积全部加起来

这样就能算出 $f=(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}]f$ 与满足 $a+b+c=n$ 的 $(a,b,c)$ 的选法总数一致。

基于状态转移的解释#

当我们对每个状态都计算了某个值时，可以把计算结果保存成一个多项式。原则上让“多项式的次数”表示“正在考虑的状态”，让“系数”表示该状态上的“计算出的值”（多数情况下是计数结果）。

简单地说，$f$ 等价于 $dp[]$，$[x^n]f$ 等价于 $dp[n]$。

在例1中，我们把“和的数值”作为状态（多项式幂次），把“能用多少种方式得到这个和”作为值（多项式系数），来更新多项式。

• 什么都还没选的状态 $\to$ $1$，或者说 $1\cdot x^0$
• 选择集合 $A$ 的元素 $\to$ $x^{2}+x^{3}$（可以理解为和为2或3的情况都只有一种，即 $dp[2]=dp[3]=1$，这里 $dp[i]$ 表示和为 $i$ 的选法数量）
• 再选择集合 $B$ 的元素 $\to$ ？？？（这里是问题）
  • 从 $B$ 中选 $2$ 时 $\to$ $(x^{2}+x^{3})x^{2}$。
  • 从 $B$ 中选 $4$ 时 $\to$ $(x^{2}+x^{3})x^{4}$。
  • 合起来 $\to$ $(x^{2}+x^{3})(x^{2}+x^{4})$。

从 $B$ 中选择元素，等价于有“把当前状态 $+2$”和“把当前状态 $+4$”的两个选项。像这样，把所有状态同时平移一个常数的操作，可以表示为乘上 $x^{n}$。于是我们可以用多项式乘法表示状态转移，然后让我们继续推导，

• 假设选完集合 $B$ 时，已经得到多项式 $g$。
• 继续选择集合 $C$ 的元素
  • 从 $C$ 中选 $3$ → $gx^{3}$。
  • 从 $C$ 中选 $5$ → $gx^{5}$。
  • 从 $C$ 中选 $7$ → $gx^{7}$。
  • 合起来 → $g(x^{3}+x^{5}+x^{7})$。

可以看到，选一个元素这件事就变成了乘上某个多项式的操作。什么都还没选的状态是 $1$，经过从 $A,B,C$ 中的选择之后，最终得到多项式 $f=(x^{2}+x^{3})(x^{2}+x^{4})(x^{3}+x^{5}+x^{7})$。

一维问题#

例2

有 $2$ 个苹果、$3$ 个橘子、$4$ 个葡萄出售。一共买 $n$ 个水果的方法有多少种？（同种水果之间不区分）

例3

苹果、橘子、葡萄都有无限多个出售。一共买 $n$ 个的方法有多少种？（同种水果之间不区分）

例4

有重量为 $w_{1}$ 的物品、重量为 $w_{2}$ 的物品、……、重量为 $w_{k}$ 的物品各 $1$ 个。装进承重 $W$ 的包中有多少种方法？（忽略装入顺序；也可以一个都不选）

例5

令 $N,M$ 为正整数。统计满足如下条件的整数列 $A_{1},\ldots,A_{N}$ 数量：

• $0<A_{1}\leq A_{2}\leq\cdots\leq A_{N}=M$
• 对任意 $1\leq i\leq N-1$，都有 $3\leq A_{i+1}-A_{i}\leq 5$

例6

令 $N,M$ 为正整数。统计满足如下条件的整数列 $A_{1},\ldots,A_{N}$ 数量：

• $0<A_{1}\leq A_{2}\leq\cdots\leq A_{N}<M$
• 对任意 $1\leq i\leq N-1$，都有 $3\leq A_{i+1}-A_{i}\leq 5$

例7

投掷标准骰子 $100$ 次。求点数之和为 $n$ 的概率。

例8

实数 $p,q$ 满足 $p+q=1$。一开始位于数轴原点，每次投掷一枚“正面概率为 $p$、反面概率为 $q$ 的硬币”，若为正面就向正方向走 $1$ 步，若为反面就向负方向走 $1$ 步。投掷硬币 $100$ 次后，位于 $x=n$ 的概率是多少？

例9

考虑把正整数 $N$ 表示为 $N=a_{1}+a_{2}+\cdots+a_{k}$（其中 $a_{i}$ 为正整数）的形式（要区分不同顺序）。对这样的分割，把它的“美丽度”定义为 $\prod_{i=1}^{k}a_{i}^{2}$。求所有分割的“美丽度”之和。

高维问题#

高维问题中多项式往往很难高速计算，除非具有很好的结构。

例10

有如下商品：

• 商品 A：价格 $3$ 元，重量 $4$ 克
• 商品 B：价格 $5$ 元，重量 $6$ 克

每种最多可以买 $2$ 个。正好花 $n$ 元、重量为 $m$ 克的方法有多少种？

例11

有无限多枚 $1$ 元、$5$ 元、$10$ 元硬币。正好使用 $n$ 枚并正好支付 $m$ 元的方法数是多少？

例12

从二维坐标平面上的原点出发，进行随机游走。也就是说，当位于 $(x,y)$ 时，反复以相等概率移动到 $(x\pm1,y)$、$(x,y\pm1)$。每 $1$ 秒移动 $1$ 次。求 $T$ 秒后位于 $(a,b)$ 的概率。

bonus：https://www.zhihu.com/question/310998719/answer/593071401。

例13

有 $3$ 个变量 $X,Y,Z$，初始时它们的值全都是 $0$。一次操作中，可以做以下任意一种：

• 选择 $1$ 个变量，加上 $1$ 或 $-1$
• 给所有变量同时加上 $1$，或同时加上 $-1$

$N$ 次操作后，满足 $X=p$、$Y=q$、$Z=r$ 的操作序列有多少种？