OI集训 Day16

Content：生成函数，多项式，期望
Date：2025.8.1

课堂内容

生成函数

定义

• 普通生成函数（OGF）：普通生成函数的定义为形式幂级数：$\displaystyle F(x) = \sum_{i} a_i x^i$
• 指数生成函数（EGF）：指数生成函数的定义为形式幂级数：$\displaystyle F(x) = \sum_{i} a_i \frac{x^i}{i!}$

普通生成函数的基本运算

• $\displaystyle F(x) \pm G(x) = \sum_{i} (a_i \pm b_i) x^i$
• $\displaystyle F(x)G(x) = \sum_{n} x^n \sum_{i=0}^n a_i b_{n-i}$
• 封闭形式。e.g.
  • $\displaystyle F(x) = \sum_{n \ge 0} x^n = \frac{1}{1-x}$
    证明：

    $$\begin{aligned} & F(x) = 1 + x + x^2 + x^3 + \dots + x^n \\ & xF(x) = x + x^2 + x^3 + x^4 + \dots + x^(n+1) \\ & \therefore F(x) - xF(x) = 1 \to F(x) = \frac{1}{1-x} \end{aligned}$$

    其他的普通生成函数也可以由这样的变换得到其封闭形式。

指数生成函数的基本运算

$$\begin{aligned} F(x)G(x) &= \sum_{i \ge 0} a_i \frac{x^i}{i!} \sum_{j \ge 0} b_j \frac{x^j}{j!} \\ &= \sum_{n \ge 0} x^n \sum_{i=0}^n \binom{n}{i} a_i b_{n-i} \frac{1}{i!(n-i)!} \\ &= \sum_{n \ge 0} \frac{x^n}{n!} \sum_{i=0}^n \binom{n}{i} a_i b_{n-i} \end{aligned}$$

即 $F(x)G(x)$ 的结果是序列 $\displaystyle \sum_{i=0}^n \binom{n}{i} a_i b_{n-i}$ 的指数生成函数。

例题

Luogu-P10780 BZOJ3028 食物

思路

我们把每个食物的生成函数学出来再相乘，得到：

$$\begin{aligned} & (\frac{1}{1-x^2})(x+1)(x^2+x+1)(\frac{x}{1-x^2})(\frac{1}{1-x^4})(x^3+x^2+x+1)(x+1)(\frac{1}{1-x^3}) \\ =& \frac{x}{x^4-4x^3+6x^2-4x+1} \\ =& \frac{x}{(x-1)^4} \end{aligned}$$

展开后得到：

$$\sum_{n \ge 1} \frac{n(n+1)(n+2)x^n}{6}$$

所以答案就为：$\displaystyle \frac{n(n+1)(n+2)}{6}$.最后，注意取模。

提交记录：link

CodeForces-280C Game On Tree

思路

由于期望具有线性性：

$$E(x+y) = E(x) + E(y)$$

所以答案就是每个点被选中的概率之和。

因为每个点被选中的概率只和这个点到根节点的长度为 $dep(u)$ 的链有关（即 $u$ 的祖先）。所以这个点被选中的概率即为 $\displaystyle \frac{1}{dep(u)}$。答案即为：

$$\sum_{u} \frac{1}{dep(u)}$$

提交记录：link