2021牛客暑期多校训练营4 B

A Course

生成函数来计数不同课的选择方案

$$\sum_{i=0}^n x^i = \frac{1}{1-x^n}\\ f_i(x) =\prod_{i \to j} f_j...$$

B Sample Game

题目概述

有一个随机数生成器可以生成$[1,n]$中所有数，每个数被生成的概率为$p_i$,该生成器如果生成的数均不小于之前生成的所有数，则继续生成，否则停止。记每一轮一共生成了$x$个数，则收益为$x^2$。问期望收益。

数据范围

$$1 \leq n \leq 100$$

分析与解

这个题巧妙之处在于对长度发生概率的设而不求。

首先我们根据题意知道除了最后一个数之外，该生成序列是单调不降的。那么一旦我们知道了每一个数被生成了多少次，则生成序列唯一确定。因此我们可以用生成函数来描述这个期望。

注意到对于一种数，它的被生成的无限期望为

$$E(\infty)=\sum_{i=1}^{\infty}p_s^i \cdot x_s^i=\frac{1}{1-p_sx_s}$$

因此从序列长度为1到长度为无穷的期望组合的描述如下

$$\begin{aligned} f(x)&=\sum_{i=1}^{\infty} \big(\sum_{s_1+s_2+...+s_n=i} \prod_{k=1}^n p_k^{s_k}) \cdot x^i\\ &=\sum_{i=1}^{\infty}P(len>i)x^i\\ &=\prod_{i=1}^n (1+p_ix_i+p_i^2x_i^2+...+p_i^{\infty}x_i^{\infty})\\ &=\prod_{i=1}^n \frac{1}{1-p_ix} \end{aligned}$$

但这个描述的目的只是间接的得到概率的关系，我们还是得考虑具体的期望公式，再设法往上面得到的这个$f(x)$上转化。

$$\begin{aligned} E&=\sum_{i=0}^{\infty}\big(P(len>i) -P(len>i+1))\cdot i^2\\ &展开后按照P(len>i)合并项得到\\ &=\sum_{i=0}^{\infty}P(len>i)[(i+1)^2-i^2]\\ &=\sum_{i=0}^{\infty}P(len>i)(2i+1)\\ &=2\cdot f'(1)+f(1) \end{aligned}$$

下面再考虑求$f’(x)$

$$\begin{aligned} 令g_i(x)&=\frac{1}{1-p_ix}\\ 则g_i'(x)&=\frac{p_i}{(1-p_ix)^2}\\ 故f'(x)&=\sum_{i=1}^{n}g_i'(x)\cdot \prod_{j \not=i}g_j(x)\\ &=f(x)\cdot \sum_{i=1}^n \frac{p_i}{1-p_ix} \end{aligned}$$

故答案就是

$$\big(1+2\cdot\sum_{i=1}^n \frac{p_i}{1-p_i})f(1)$$