YbtOJ 976「母函数」随机减法
题目链接：YbtOJ #976
小 A 有一个长度为 $n$ 的序列 $a$ 和一个初始值为 $0$ 的计数器 $cnt$，他想要对其进行 $k$ 次操作。
每次操作，他会等概率随机选中一个 $i$，将 $a_i$ 减 $1$，并将 $cnt$ 加上 此时 除 $a_i$ 以外所有数的乘积，即 $\prod_{j\not=i}a_j$。
现在，他希望知道 $cnt$ 在模 $10^9+7$ 意义下的期望值。
$1\le n\le5\times10^3$，$1\le k\le10^9$，$0\le a_i < 10^9+7$。
Solution
容易发现将 $a_i$ 减 $1$ 后，除它以外所有数的乘积恰好是 $\prod_{i=1}^na_i$ 的变化量。
所以说，答案实际上就是原本的 $\prod_{i=1}^na_i$ 减去修改后 $\prod_{i=1}^na_i’$ 的期望值。
设 $f_{i,j}$ 表示前 $i$ 个数一共修改了 $j$ 次的所有方案下乘积之和，则：
$$
f_{i,p+q}=\sum C_{p+q}^p\times (a_i-p)\times f_{i-1,q}
$$
于是：
$$
\frac{f_{i,p+q}}{(p+q)!}=\sum\frac{a_i-p}{p!}\times\frac{f_{i-1,q}}{q!}
$$
设 $F_i(x)=\sum_{p=0}^{+\infty}f_{i,p}\frac{x^p}{p!},G_i(x)=\sum_{p=0}^{+\infty}(a_i-p)\frac{x^p}{p!}$，得到：
$$
F_i(x)=F_{i-1}(x)*G_i(x)
$$
因此只要把 $G_{1\sim n}(x)$ 这 $n$ 个生成函数卷起来就能得到 $F_n(x)$，而它的 $k$ 次项系数就是 $\frac{f_{n,k}}{k!}$ 了。
对于 $G_i(x)$，我们把 $a_i-p$ 分开来：
$$
G_i(x)=a_i\sum_{p=0}^{+\infty}\frac{x^p}{p!}-\sum_{p=0}^{+\infty}\frac{x^{p+1}}{p!}=(a_i-x)e^x
$$
设 $A_i(x)=a_i-x$，发现 $F_n(x)$ 就是 $A_{1\sim n}(x)$ 这 $n$ 个生成函数卷起来之后再卷上 $e^{nx}$。
很容易 $O(n^2)$ 暴力求出 $A_{1\sim n}(x)$ 卷起来后每一项的系数 $f_i$，于是：
$$
F_n(x)=(\sum_{i=0}^{+\infty}f_ix^i)*(\sum_{i=0}^{+\infty}\frac {(nx)^i}{i!})\
[x^k]F_n(x)=\sum_{i=0}^kf_i\times\frac{n^{k-i}}{(k-i)!}
$$
乘上一个 $k!$ 得到了总和 $f_{n,k}$，再除以总方案数 $n^k$ 得到期望：
$$
E=\sum_{i=0}^{k}\frac{f_i\times k^{\underline i}}{n^i}
$$
最终答案就是$\prod_{i=1}^na_i-E$。
注意一开始卷积直接暴力卷即可。
Code
1 |
|