wiki - 算法小站

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

数学

组合计数

二项式定理

生成函数（一）

[[ item.c ]]

生成函数（一）

## 问题引入
求一个关于指标集$$I$$的解，比如定义$$I$$，$$x + y + z \leqslant n$$的所有正整数解的个数
记为$$f(n)$$，对于所有$$\forall n \in I = \mathbb{Z}\_{\geqslant 0} = \\{0, 1, \cdots, \\}$$
可以得到$$f(0), f(1), \cdots$$

### 多项式和形式幂级数
多项式，比如说$$A(x) = \sum\_{i = 0}^{n} a\_i x^{i}$$

形式幂级数$$S(x) = \sum\_{i \geqslant 0} a\_i x^{i}$$

其中$$a_i \in K$$，$$K$$是一个域，通常我们考虑$$K = \mathbb{R}$$或者$$K = \mathbb{Z}_p$$

### 形式幂级数的运算
不妨设$$A(x) = \sum\_{i \geqslant 0} a\_i x^i, B(x) = \sum\_{i \geqslant 0}b\_i x^i$$

加法，$$A(x) + B(x) = \sum\_{i \geqslant 0} (a_i + b_i)x^i$$

减法，$$A(t) - B(t) = \sum\_{i \geqslant 0} (a_i - b_i)x^i$$

乘法，$$A(x)B(x) = \sum\_{k \geqslant 0}\left(\sum\_{i+j = k}a_ib_j \right)x^k$$

形式幂级数在以上定义的$$+, -, \times$$，形成一个环

**记号**
形式幂级数（多项式）$$A(x)$$的$$x^n$$这一项的系数是$$[x^n]A(x)$$

## 常生成函数（OGF）
一个数列$$\\{a\_n\\}$$对应的常生成函数是$$A(x) = \sum\_{n \geqslant 0}a\_nx^n$$

**例1**
有两种物体，其中取第$$i$$个第一种物体的方案数是$$a_i$$，取$$j$$个第二种物体的方案数是$$b_j$$
求取$$k$$个物体的方案数

**算法分析**
实际上，枚举第一个物品取$$i$$个，答案就是
```math
\displaystyle
\sum_{i = 0}^{k} a_i b_{k - i}
```
假设第一种物品对应的 OGF 是$$A(x)$$，第二种物品对应的 OGF 是$$B(x)$$
那么答案就是$$[x^k]A(x)B(x)$$

**例2**
在一个水果店，有苹果，香蕉，草莓三种水果，你可以取$$n$$个水果
但是水果店要求，取的苹果数必须是偶数，取的香蕉数必须是$$3$$的倍数
取的草莓数不能超过$$5$$个，问取$$n$$种水果的方案

**算法分析**
假设只有一种水果，苹果有无限多，不同苹果之间**不做区分**
那么取$$i$$个苹果的方案数记为$$a_i$$，我们有$$a_0 = 1, a_1 = 0, a_2 = 1, \cdots$$
（因为只能取偶数，并且不同苹果之间不做区分，取`2`个苹果实际上也只有`1`种取法）
那么对于苹果，它的 OGF 为$$A(x) = 1 + x^2 + x^4 + \cdots$$

同理，对于香蕉，它的 OGF 对应是$$B(x) = 1 + x^3 + x^6 + x^9 + \cdots$$

而对于草莓，它只能取`5`个，那么$$C(x) = 1 + x + x^2 + x^3 + x^4 + x^5$$

记$$S(x) = A(x)B(x)C(x)$$，可以$$O(n^2)$$暴力，注意每次只保留前$$n$$项
最后的答案是$$[x^n]S(x)$$

**例3 不定方程解的数量**
求不定方程$$x_1 + x_2 + \cdots + x_k = n$$的解的数量，要求$$l_i \leqslant x_i \leqslant r_i$$

假设$$k = 2$$，对于$$x_1 + x_2 = n$$
那么$$x_1$$这一种物品可以选多少个呢？可以选$$[l_1, r_1]$$个
```math
\displaystyle
F_1(x) = x^{l_1} + x^{l_1 + 1} + \cdots + x^{r_1} \\
F_2(x) = x^{l_2} + x^{l_2 + 1} + \cdots + x^{r_2} \\
\vdots \\
F_i(x) = \sum_{j = l_i}^{r_i} x^j
```
最后要求的是
```math
F(x) = \prod_{i = 1}^{k} F_i(x) \quad ans = [x^n]F(x)
```

再比如求$$x_1 + 2x_2 + 3x_3 = n$$的正整数解的个数
实际上，可以看作`3`类物品，第一类物品没有限制，第二类物品必须是`2 的倍数`
第三类物品必须是`3 的倍数`，求方案数
三类物品对应的 OGF 分别是
```math
\displaystyle
F_1(x) = \sum_{i \geqslant 1} x^i = x + x^2 + x^3 + \cdots \\
F_2(x) = \sum_{i \geqslant 1, 2 \mid i} x^i = x^2 + x^4 + x^6 + \cdots \\
F_3(x) = \sum_{i \geqslant 1, 3 \mid i} x^i = x^3 + x^6 + x^9 + \cdots \\

F(x) = F_1(x)F_2(x)F_3(x), \quad ans = [x^n]F(x)
```

### 常生成函数定理
设$$S = \\{a_1, a_2, \cdots, a_k\\}$$，且$$a_i$$可以取的**次数**的集合是$$M_i$$

那么记$$F\_i(x) = \sum\_{u \in M\_i}x^u$$，则从$$S$$中取$$n$$个元素组成集合的方案数$$g(n)$$对应的 OGF 是
```math
\displaystyle
G(x) = \sum_{i \geqslant 0}g(i)x^i \\

G(x) = F_1(x)F_2(x)\cdots F_k(x)
```

## 形式幂级数的逆元
形式幂级数$$A(x)$$的逆元，$$A(x)B(x) = 1$$
逆元存在的条件，$$[x^0]A(x) \neq 0$$
可以暴力递推来计算
```math
\displaystyle
A(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n \\
B(x) = b_0 + b_1x + b_2x^2 + \cdots + b_nx^n \\
A(x)B(x) = a_0b_0 + (a_0b_1 + a_1b_0)x^1 + (a_0b_2 +a_1b_1 +a_2b_0)x^2 + \cdots  \\
+ (a_0b_n + a_1b_{n-1} + \cdots + a_nb_0)x^n
```
暴力递推如下
```math
a_0b_0 = 1 \Rightarrow b_0 = a_0^{-1} \\
b_1 = -(a_1b_0) \cdot a_0^{-1} \\
\vdots \\
b_n = -(a_1b_{n-1} + \cdots + a_nb_0) \cdot a_0^{-1}
```
### 常见的逆元
```math
\displaystyle
A(x) = 1 + x + x^2 + \cdots, \quad B(x) = 1 - x \Rightarrow \dfrac{1}{1-x} = \sum_{i \geqslant 0} x^i \\
\quad \\
A(x) = 1 + ax + a^2x^2 + \cdots, \quad B(x) = 1 - ax \Rightarrow \dfrac{1}{1-ax} = \sum_{i \geqslant 0} a^ix^i \\
\quad \\
A(x) = \binom{k-1}{0} + \binom{k}{1}x + \binom{k+1}{2}x^2 + \binom{k+2}{3}x^3 + \cdots, \quad B(x) = (1 - x)^k \\
\Rightarrow \dfrac{1}{(1-x)^k} = \sum_{i \geqslant 0}\binom{i+k-1}{i}x^i
```

## OGF 的一些问题
### 牛客IOI周赛20-提高组A
**[背包](https://ac.nowcoder.com/acm/contest/24710/A)**
一共有`8`种物品，肥宅快乐水，鸡腿，鸡翅，鸡块，鸡汤，鸡蛋，大盘鸡，啤酒鸡
求带$$n$$个的方案数
要求肥宅快乐水最多`1`个，鸡汤奇数个，大盘鸡最多`2`个，鸡块个数为`4`的倍数
啤酒鸡最多`3`个，鸡腿最多`1`个，鸡翅偶数个，鸡蛋个数是`3`的倍数

**算法分析**
```math
\displaystyle
F_1(x) = 1 + x = \dfrac{1-x^2}{1-x} \\
F_2(x) = x + x^3 + x^5 + \cdots = x \cdot \dfrac{1}{1-x^2} \\
F_3(x) = 1 + x + x^2 = \dfrac{1-x^3}{1-x} \\
F_4(x) = 1 + x^4 + x^8 + \cdots = \dfrac{1}{1-x^4} \\
F_5(x) = 1 + x + x^3 + \cdots = \dfrac{1-x^4}{1-x} \\
F_6(x) = 1 + x = \dfrac{1-x^2}{1-x} \\
F_7(x) = 1 + x^2 + x^4 + x^6 + \cdots = \dfrac{1}{1-x^2} \\
F_8(x) = 1 + x^3 + x^6 + x^9 + \cdots = \dfrac{1}{1-x^3}
```
不难发现，对应的 OGF 是$$F(x) = \dfrac{x}{(1-x)^4}$$
```math
\displaystyle
F(x) = x \cdot \sum_{i \geqslant 0}\binom{i+3}{3}x^i = \sum_{i \geqslant 1} \binom{i+2}{3}x^i
```
最后的答案是$$\displaystyle [x^n]F(x) = \binom{n+2}{3}$$

### codeforces 451E
**[Devu and Flowers](https://ac.nowcoder.com/acm/contest/24710/B)**
有`n`种花，分别有$$f_1, f_2, \cdots, f_n$$个，求取`s`朵花的方案数
注意$$n \in [1, 20]$$，$$f_i, s \leqslant 10^{14}$$

**算法分析**
不难写出 OGF
```math
\displaystyle
F(x) = \dfrac{\prod_{i = 1}^{n} (1 - x^{f_i + 1})}{(1-x)^n}
```
因为$$s$$很大，直接求$$[x^s]F(x)$$不可取，但是$$n$$只有`20`，记
```math
\displaystyle
A(x) = \prod_{i = 1}^{n} (1 - x^{f_i + 1}) \Rightarrow F(x) = A(x) \cdot \dfrac{1}{(1-x)^n}
```
其中
```math
\displaystyle
[x^s]F(x) = \sum_{i} [x^i]A(x) \cdot [x^{s-i}]\dfrac{1}{(1-x)^n} = \sum_{i\leqslant s}[x^i]A(x) \cdot \binom{s-i+n-1}{n-1}
```
因为$$A(x)$$只有$$O(2^n)$$项，可以暴力`dfs`求出每一个$$x^i$$的系数
```bash
void solve(int cas) {
    int n;
    i64 s;
    cin >> n >> s;

comb.init(LOG+5);

vector<i64> f(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> f[i];
        f[i] += 1;
    }

map<i64, i64> coef;
    auto dfs = [&](auto &dfs, int i, i64 pw, i64 C) -> void {
        if (i >= n) {
            coef[pw] += C;
            return;
        }

dfs(dfs, i+1, pw, C);
        dfs(dfs, i+1, pw + f[i], -C);
    };
    dfs(dfs, 0, 0, 1);

auto binom = [&](i64 n, i64 m) -> mint {
        if (n < m or m < 0) return mint(0);
        auto B = comb.invfac(m);

i64 x = n;
        mint A = 1;
        for (int i = 0; i < m; i++) {
            A *= mint(x), x -= 1;
        }

return A * B;
    };

mint ans = 0;
    for (auto [i, C] : coef) {
        // C x^i
        if (s - i < 0) continue;
        mint res = mint(C) * binom(s+n-i-1, n-1);
        ans += res;
    }
    cout << ans << "\n";
}
```

### CEOI2004
**[CEOI2004 Sweets](https://ac.nowcoder.com/acm/contest/24710/C)**
有`n`种糖果，每一种分别有$$m_1, m_2, \cdots, m_n$$个，求取不少于$$a$$不多于$$b$$颗糖果的方案数

**算法分析**
与上一个问题类似，可以写出 OGF 是
```math
\displaystyle
F(x) = \dfrac{\prod_{i=1}^{n} (1-x)^{m_i + 1}}{(1-x)^n} \Rightarrow A(x) = \prod_{i=1}^{n} (1-x)^{m_i + 1} \\

F(x) = A(x) \cdot \dfrac{1}{(1-x)^n}
```
最后的答案是
```math
\displaystyle
\sum_{s = a}^{b} [x^s]F(x) = \sum_{s = a}^{b} \sum_{i \leqslant s} [x^i]A(x) \cdot \binom{s-i+n-1}{n-1}
```
不难发现，这样直接做，还需要$$O(b - a)$$的额外代价，可以进一步化简
```math
\displaystyle
\sum_{i \leqslant s}[x^i]A(x) \left( \sum_{s = a}^{b} \binom{s-i+n-1}{s-i}  \right) \\
\Rightarrow s-i = s' 
```
不难发现，括号内的求和表达式可以化简成
```math
\displaystyle
s \leftarrow s' \\
\sum_{s = a-i}^{b-i} \binom{n-1+s}{s} = sum(b - i) - sum(a-i-1)
```
现在考虑**平行求和法**（见二项式部分）
```math
\displaystyle
sum(b - i) = \sum_{s = 0}^{b-i} \binom{n - 1 + s}{s} = \binom{(n-1)+(b-i)+1}{b-i} = \binom{n+b-i}{b-i}
```
最后的答案是
```math
\displaystyle
\sum_{i \leqslant s}[x^i]A(x) \left( \binom{n+b-i}{b-i} - \binom{n+a-i-1}{a-i-1} \right)
```
> 组合数取模，在模非素数的情况下
根据
```math
\displaystyle
\dfrac{A}{B} \bmod m = \dfrac{A \bmod (Bm)}{B}
```
这样避免求逆元的情况，因为$$\text{gcd}(A, m) \neq 1$$的情况下，不一定有逆元

## 递推关系和生成函数
斐波那契数列满足$$a\_0 = 1, a\_1 = 1, a\_n = a\_{n-1} + a\_{n-2}(n \geqslant 2)$$
求其常生成函数

**算法分析**
```math
\displaystyle
A(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n + \cdots \\
= a_1x + (a_0 + a_1)x^2 + (a_1 + a_2)x^3 + \cdots + (a_{n-2} + a_{n-1})x^n + \cdots \\
= x + (a_0x^2 + a_1x^3 + \cdots + a_{n-2}x^n + \cdots) \\
+(a_1x^2 + a_2x^3 + \cdots + a_{n-1}x^n + \cdots) \\
= x + x^2A(x) + x(A(x) - a_0)
```
化简之后可以得到
```math
\displaystyle
A(x) = \dfrac{x}{1-x-x^2}
```
求解生成函数的形式幂级数展开，可以用**待定系数法**
```math
\displaystyle
A(x) = \dfrac{x}{1-x-x^2} = \dfrac{c}{1-ax} + \dfrac{d}{1-bx} 
```
可以求出
```math
\displaystyle
a = \dfrac{1+\sqrt{5}}{2}, b = \dfrac{1-\sqrt{5}}{2}, c = \dfrac{1}{\sqrt{5}}, d = -\dfrac{1}{\sqrt{5}}
```
从而
```math
\displaystyle
[x^n]A(x) = ca^{n} + db^n = \dfrac{1}{\sqrt{5}} \left( \left( \dfrac{1+\sqrt{5}}{2} \right)^n - \left( \dfrac{1-\sqrt{5}}{2} \right)^n  \right)
```

**一般情况**
```math
\displaystyle
a_n = c_1a_{n-1} + c_2a_{n-2} + \cdots + c_ka_{n-k}
```

对应的常生成函数$$A(x) = \sum\_{n \geqslant 0} a_nx^n$$

> 证明

```math
\displaystyle
A(x) = a_0 + a_1x + \cdots + a_{k-1}x^{k-1} \\
+ \sum_{n \geqslant k} (c_1a_{n-1} + \cdots + c_ka_{n-k})x^n \\
= a_0 + a_1x + \cdots + a_{k-1}x^{k-1} \\
+ c_1x(A(x) - (a_0 + a_1x + \cdots + a_{k-2}x^{k-2})) \\
+ c_2x^2(A(x) - (a_0 + a_1x + \cdots + a_{k-3}x^{k-3})) \\
+ \cdots + c_kx^{k}A(x) \\
\vdots \\
\Rightarrow A(x) = \dfrac{B(x)}{1 - (c_1x + c_2x^2 + \cdots c_kx^k)} \\
= \dfrac{v_1}{1-u_1x} + \dfrac{v_2}{1-u_2x} + \cdots
```

### catalan 数和生成函数
考虑$$n+1$$个数相乘，$$x_0x_1x_2\cdots x_n$$，求他们结合顺序的方案数
比如$$n = 3$$时，有5种方案
```math
\displaystyle
x_0(x_1(x_2x_3)), x_0((x_1x_2)x_3), (x_0x_1)(x_2x_3), (x_0(x_1x_2))x_3, ((x_0x_1)x_2)x_3
```

**算法分析**
记方案数为$$f(n)$$，考虑最后一次
```math
(x_0x_1\cdots x_i)(x_{i+1}\cdots x_n)
```

方案数可以记为$$\displaystyle f(n) = \sum\_{i = 0}^{n-1}f(i)f(n-i-1)$$
其中$$f(0) = f(1) = 1$$
**递推公式**
```math
\displaystyle
c_0 = 1, c_1 = 1 \\
c_n = c_0c_{n-1} + c_1c_{n-2} + \cdots + c_{n-1}c_0
```
**定义生成函数**
```math
\displaystyle
C(x) = \sum_{n\geqslant 0}c_nx^n \\
c_0 = c_1 = 1, c_{n+1} = \sum_{i = 0}^{n}c_ic_{n-i}
```
将最后的表达式两边同时$$\times x^{n+1}$$，并对$$n \geqslant 0$$求和
左边
```math
\displaystyle
\sum_{n\geqslant 0}c_{n+1}x^{n+1} = C(x) - c_0x^0 = C(x) - 1
```
右边
```math
\displaystyle
\sum_{n \geqslant 0}\left( \sum_{i=0}^{n}c_ic_{n-i} \right)x^{n+1} = x\sum_{n \geqslant 0} \left(\sum_{i=0}^{n}c_ic_{n-i} \cdot x^n \right) = xC(x)^2
```
最后一项实际上是卷积的形式，可以得到
```math
\displaystyle
C(x) - 1 = xC(x)^2
```
最后求出来
```math
\displaystyle
C(x) = \dfrac{1-\sqrt{1-4x}}{2x}
```
说明，这里不能取$$1 + \sqrt{1-4x}$$，如果这样的话，$$C(0) = \infty$$
而我们期望的$$C(0) = 1$$

> 推导

以下第一步根据吸收公式
```math
\displaystyle
\sqrt{1-4x} = \sum_{k \geqslant 0} \binom{\frac{1}{2}}{k}(-4x)^k = 1 + \sum_{k \geqslant 1} \dfrac{1}{2k}\binom{-1/2}{k-1}(-4x)^k
```
那么
```math
\displaystyle
\dfrac{1-\sqrt{1-4x}}{2x} = \sum_{k \geqslant 1}\dfrac{1}{k} \binom{-1/2}{k-1}(-4x)^{k-1} \\
= \sum_{n\geqslant 0} \dfrac{1}{n+1} \binom{-1/2}{n} (-4x)^n
```

> 根据广义二项展开
```math
\displaystyle
\dfrac{(-\frac{1}{2}) (-\frac{1}{2}-1) \cdots (-\frac{1}{2}-n+1)}{n!} (-4)^n \\
= \dfrac{(-\frac{1}{2}) (-\frac{1}{2}-1) \cdots (-\frac{1}{2}-n+1) \cdot n!}{n!n!} (-4)^n \\
= \dfrac{(-1)^n(\frac{1}{2}) (\frac{1}{2}+1) \cdots (\frac{1}{2}+n-1)}{n!n!} (-4)^n \\
\vdots \\
= \dfrac{(1\cdot 3 \cdots \cdot (2n - 1))(2 \cdot 4 \cdots 2n)}{n!n!} = \binom{2n}{n}
```

综上所述
```math
\displaystyle
C(x) = \sum_{n \geqslant 0} \dfrac{1}{n+1}\binom{2n}{n} x^n \\ 
c_n = \dfrac{1}{n+1} \binom{2n}{n}
```

## 指数生成函数
一个数列$$\\{a\_n\\}$$对应的指数生成函数是$$A(x) = \sum\_{n \geqslant 0}a\_n \dfrac{x^n}{n!}$$

比如给定序列$$\\{1, 1, \cdots, 1, \cdots\\}$$
```math
\displaystyle
A(x) = 1 + x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdots = e^x
```

**例1**
有`2`种物体，其中取$$i$$个第`1` 种物品的方案数为$$a_i$$，取$$j$$个第`2`种物品的方案数为$$b_j$$
求取$$k$$个物品并排成一列的方案数

可以考虑枚举第`1`种物品选了多少个
```math
\displaystyle
c_k = \sum_{i = 1}^{k} \binom{k}{i}a_ib_{k-i} = \sum_{i=1}^{k}\dfrac{k!}{i!(k-i)!}a_ib_{k-i} \\
\Rightarrow \dfrac{c_k}{k!} = \sum_{i = 0}^{k} \dfrac{a_i}{i!} \dfrac{b_{k-i}}{(k-i)!}
```
不妨记
```math
\displaystyle
A(x) = a_0 + a_1\dfrac{x}{1!} + a_2\dfrac{x^2}{2!} + \cdots + a_n\dfrac{x^n}{n!} \\
B(x) = b_0 + b_1\dfrac{x}{1!} + b_2\dfrac{x^2}{2!} + \cdots + b_n\dfrac{x^n}{n!}
```
那么
```math
\displaystyle
C(x) = \sum_{k \geqslant 0}\dfrac{c_k}{k!}x^k = \sum_{k\geqslant 0} \sum_{i = 0}^{k} \dfrac{a_i}{i!} x^i \dfrac{b_{k-i}}{(k-i)!} x^{k-i} = A(x)B(x)
```

**例2**
用`1, 2, 3, 4`作为`6`位数，每个数字在`6`位数中出现的次数不能大于`2`
求能作出多少个`6`位数？

**算法分析**
实际上是`1, 2, 3, 4`总共取`6`个数，然后排成一列
```math
\displaystyle
6! \left([x^6](1 + x + \dfrac{x^2}{2!})^4 \right)
```

### 指数生成函数定理
记$$S = \\{a_1, a_2, \cdots, a_k\\}$$，设$$a_i$$可以取的次数的集合是$$M_i$$
```math
\displaystyle
F_i(x) = \sum_{u \in M_i}\dfrac{x^u}{u!}
```
则从$$S$$中取`n`个元素排成一列的方案数$$g(n)$$的指数生成函数
```math
\displaystyle
G(x) = \sum_{i \geqslant 0}g(i)\dfrac{x^i}{i!}, \quad G(x)=F_1(x)F_2(x)\cdots F_k(x)
```
公式
```math
\displaystyle
exp(x) = 1 + x + \dfrac{x^2}{2!} + \cdots = \sum_{n \geqslant 0} \dfrac{x^n}{n!} \\
exp(ax) = 1 + ax + a^2\dfrac{x^2}{2!} + \cdots = \sum_{n \geqslant 0} a^n\dfrac{x^n}{n!}
```

## 指数生成函数的一些问题
### Blocks
**[Blocks](https://ac.nowcoder.com/acm/contest/24710/D)**
给定一个长度是`n`的序列，每个格子可以被涂成红、蓝、绿或者黄，只能有偶数个红色格子和绿色格子，求涂色的方案数

**算法分析**
原问题相当于有`红，蓝，绿，黄`的格子若干，每一个格子能选$$a_i, b_i, c_i, d_i$$次
要求$$a_i + b_i + c_i + d_i = n$$，把这`n`个格子拍成一列，问不同排列的方案数

红和绿有限制，生成函数记为$$F(x)$$
蓝和黄没有限制，生成函数记为$$G(x)$$
最后的答案是，记$$H(x) = F(x)^2 G(x)^2 \Rightarrow n![x^n]H(x)$$

```math
\displaystyle
F(x) = 1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + \cdots = \dfrac{e^x + e^{-x}}{2} \\
\quad \\
G(x) = 1 + x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdots = e^x
```
最后化简
```math
\displaystyle
H(x) = \dfrac{e^{4x} + 2e^{2x} + 1}{4} = \sum_{n \geqslant 0} \dfrac{1}{4} \left(4^n + 2 \cdot 2^n \right) \dfrac{x^n}{n!} + \dfrac{1}{4}
```
所求的答案是
```math
\displaystyle
n![x^n]H(x) = \dfrac{1}{4}(4^n + 2 \cdot 2^n) = 4^{n-1} + 2^{n-1}
```

### Lust
**[Lust](https://ac.nowcoder.com/acm/contest/24710/E)**
给定`n`个数$$a[1\cdots n]$$，进行$$k$$次操作，每一次随机选择一个数$$x \in [1, n]$$
将$$a_x - 1$$，并把答案增加除了$$a_x$$外所有数的乘积
求答案的期望

**算法分析**
**重要的化归**，假设当前选的是$$x$$
```math
\displaystyle
res += (a_1a_2\cdots a_x \cdots a_n) - (a_1a_2 \cdots (a_x - 1) \cdots a_n)
```
可以看作一次操作，`a[1...n]`中就有一个数减少`1`，那么$$k$$次操作之后
对于$$a_1, a_2, \cdots a_n$$分别减少的量记为$$x_1, x_2 \cdots x_n$$
其中$$x_1 + x_2 + \cdots + x_n = k$$，那么
```math
\displaystyle
res = a_1a_2\cdots a_n - (a_1 - x_1)(a_2 - x_2) \cdots (a_n - x_n)
```
求`res`的期望，实际上就是求后面这一项的期望

> 求$$\mathbb{E}[ (a_1 - x_1)(a_2 - x_2) \cdots (a_n - x_n) ]$$

```math
\displaystyle
\dfrac{\sum_{x_1+x_2+\cdots + x_n = k} (a_1-x_1)(a_2-x_2)\cdots (a_n-x_n) \cdot \text{对应的方案数} }{n^k} \\
= \dfrac{\sum_{x_1+x_2+\cdots + x_n = k} (a_1-x_1)(a_2-x_2)\cdots (a_n-x_n) \cdot \binom{k}{x_1, x_2, \cdots, x_n} }{n^k} \\
\vdots \\
= \dfrac{k!}{n^k} \sum_{x_1,x_2, \cdots, x_n} \dfrac{(a_1-x_1)}{x_1!}\dfrac{(a_2-x_2)}{x_2!}\cdots \dfrac{(a_n-x_n)}{x_n!}
```
定义生成函数
```math
\displaystyle
F_i(x) = \sum_{j \geqslant 0}\dfrac{(a_i - j)}{j!} x^j
```
那么最后我们要求的就是$$[x^k]F_1(x)F_2(x)\cdots F_n(x)$$

> 考虑$$F_i(x)$$的展开

```math
\displaystyle
F_i(x) = \sum_{j \geqslant 0} a_i \dfrac{x^j}{j!} - \sum_{j \geqslant 0} \dfrac{1}{(j-1)!}x^j \\
= a_ie^x - xe^x = (a_i - x)e^x
```
那么
```math
\displaystyle
F(x) = \left(\prod_{i=1}^{n} (a_i - x) \right) e^{nx}
```
因为$$n \leqslant 5000$$，对于
```math
A(x) = \prod_{i=1}^{n} (a_i - x)
```
可以暴力$$O(n^2)$$计算，最后的答案是
```math
\displaystyle
\sum_{i = 0}^{n} [x^i]A(x) \cdot [x^{k-i}]e^{nx} \\
= \sum_{i = 0}^{n} [x^i]A(x) \cdot \dfrac{n^{k-i}}{(k-i)!}
```
最后算出来，还要再乘以$$\dfrac{k!}{n^k}$$
```math
\displaystyle
ans = \sum_{i = 0}^{n} [x^i]A(x) \dfrac{k(k-1)\cdots (k-i+1)}{n^i}
```
最多就`n`项

#### 算法实现
```bash
vector<i64> operator * (const vector<i64> &a, const vector<i64> &b) {
    // poly, 0-index
    int n = a.size(), m = b.size();
    vector<i64> c(n+m-1);

for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            c[i+j] = c[i+j] + (1LL * a[i] * b[j] % MOD);
            safeMod(c[i+j], MOD);
        }
    }
    return c;
}

void solve(int cas) {
    int n, K;
    cin >> n >> K;

vector<i64> a(n+1);
    for (int i = 1; i <= n; i++) cin >> a[i];

vector<i64> coef(1, 1);
    for (int i = 1; i <= n; i++) {
        vector<i64> poly(2, 0);
        poly[0] = a[i], poly[1] = -1;

coef = coef * poly;
    }

comb.init(n+5);

vector<mint> depw(n+5, 0);
    depw[0] = 1;
    for (int i = 1; i <= n; i++) {
        depw[i] = depw[i-1] * mint(K-i+1);
    }

mint res = 0;
    for (int i = 0; i <= n; i++) {
        mint A = depw[i];
        mint B = power(mint(n), i);
        mint C = A / B;

res += coef[i] * C;
    }

mint tot = 1;
    for (int i = 1; i <= n; i++) tot *= mint(a[i]);

mint ans = tot - res;
    cout << ans << "\n";
}
```

看完文章有啥想法

算法小站

wiki 主题

数学

生成函数（一）

目录