B
$[1,n]$ 的数，每个数以 $p_i$ 概率生成。
重复下列操作
产生一个随机数。
if 随机数大于等于之前所有数，$goto \space 1$， else $goto \space 3$
如果产生了 $x$ 个数，获得 $x^2$ 的分数，停下。
求期望分数。
$Solution$：常用套路，因为要求平方。
而 $E((X+1)^2)=E(X)^2+2*E(X)+1$ ，其递增不线性，故要分别维护一次项和平方项的期望。
设 $f_i$ 表示当前取得的最大数是 $i$ ，还能进行的操作轮数的期望。
设 $g_i$ 表示当前取得的最大数是 $i$ ，还能进行的操作轮数的期望的平方。
转移就是枚举所有的后继，相应的概率乘上能带来的收益即可。
$$ f_i =\sum_{j = i}^{n} p_j (f_j+1)+\sum_{j = 1}^{i-1}p_j 1 $$
$$ g_i =\sum_{j = i}^{n} p_j (g_j+2 f_j+1)+\sum_{j = 1}^{i-1}p_j * 1 ^2 $$
整理一下可以分离一下 $f_i$ ， $g_i$ 系数可以得到 $$ f_i =\frac{1+\sum_{j = i+1}^{n}p_j*f_j}{1-p_i} $$
$$g_i=\frac{ 1 + 2 * p_i * f_i + \sum_{j=i+1}^{n}p_j*(g_j+2*f_j)}{1-p_i}$$
这样就可以倒推得到所有的 $f$ ，$g$ 。
注意求出的是还能进行的操作轮数的期望，那么实际答案还需加上取到这个数的一次，故对每个 $i$ 的答案是 $g_i+2*f_i+1$，乘上对应的概率就可以得到答案。
发现 $O(n)$ 维护后缀和即可做完。
E
题意： $n$ 个结点的树，每个点权介于一定范围 $[l_i,r_i]$ ，边权是点权的异或值，给定边权，求有多少种可能的点权序列。
分析：
发现已知一个点的值 $a$ ，比如说 $w_1=a$，那么你可以唯一确定得到所有 $w_ i$ 的值。
于是题目就变成了，求 $n$ 个等式限制下 $a$ 的取值个数。
$l_i \leq w_i \oplus a \leq r_i$
这 $n$ 个等式下的所有区间交长度就是我们的答案，即满足所有限制条件的 $a$ 。
考虑将所有值域放在线段树上，求 $a$ 的合法取值的区间个数。
这个可以类似之前几天题目来做，在动态开点的线段树上依次判断区间。
比如对于一个式子 $w_i \oplus a \leq r_i$，最多能确定线段树上递归 $30$ 次，并能判断一些不合法的 $a$ 的取值区间，线段树和字典树差不多。
最后递归求线段树上依然合法的区间即可。
G
给 $n$ ，$k$ ，$D$，求所有满足
- $\forall i \in[1,n],a_i \geq 0$
- $\sum _{i=1}^n a_i=D$
的 $a_i$序列的 $\frac{D!} {\prod_{i=1}^n (a_i+k)!} $。
$(n,k \leq 50,D\leq 10^8)$
考虑构造
$f(x)=\frac{1}{k!}x^0+\frac{1}{(k+1)!}x^1+\frac{1}{(k+2)!}x^2+…$
显然题目就是要求 $(f(x))^n$ 的 $x^D$ 次项系数，再乘上 $fac(D)$ 即可。
$D$ 值域较大，但只需要一个，可以分段打表。
发现 $f(x)*x^k = e^x - (1+\frac{1}{1!}x^1+ … \frac{1}{(k-1)!} x^{k-1} )$。
设 $g(x)=1+\frac{1}{1!}x^1+ … \frac{1}{(k-1)!} x^{k-1}$
$(f(x))^n= (\frac{e^x-g(x)}{x^k})^n$
显然只需求分子的 $D+k*n$ 项系数。
$(e^x-g(x))^n=\sum _{i=0}^n (-1)^i C_n^i (e^x)^{n-i}* g(x)^i$
对每个 $i$ ，枚举 $g(x)$ 的 $x$ ，容易算得对应的系数。
复杂度大概每次乘一个 $k$ 次多项式，最高指数到 $k*n$ 。
估摸着复杂度上界在 $O(n^2k+n^2k*log_2(kn))$。
感觉非常的有实力。