AT_arc180_f [ARC180F] Yet Another Expected Value

· · 题解

这篇题解只是翻译了一下 at 上的题解，并做了一些补充，有错可以直接开喷（

UPD：应该把 f(y,x) \exp 直接改成 \dfrac{1}{1-x}，最终答案不乘 n! 是可行的，也就是只枚举 x_1<x_2<\dots <x_n 的方案（拜谢 鲤鱼江 大蛇）

我们转化一下这个式子，把 1 改为 y^A，所以原式变为

\prod_{i=1}^N(y^{A} +\sum_{j=i+1}^{N}x_j^{A})

我们根据新的式子，转化一下题面：现在 n 个变量在 [0,y] 内均匀随机，而且我们要求 x_1<x_2<\dots<x_n，问答案期望。这里要求 x_1<x_2<\dots<x_n 是指如果不满足对答案的贡献为零，意思是方案集合没改变，只是不会计数非法答案。

我们设 a_{n}(y) 表示新问题的答案，那么原问题的答案即为 a_n(1)\times n!。

下一步，我们考虑 a_n(y) 的生成函数，即 f(y,x)=\sum\limits_{i\ge0}a_i(y)x^i，直接做这个式子比较困难，我们考虑能不能递推答案。

我们考虑用树结构来描述这个问题，因为这是一堆多项式乘起来，在第 i 个多项式内只会乘 y^A 或 j\ge i+1 的 x^{A}_j，我们考虑如果在该多项式内乘的是 x^A_j 那么 i 连向 j；乘的是 y^A，则 i 连向 n+1，如此构成一个树结构，[x^n]f(y,x)|_{y=1} 即为答案。

我们考虑一棵子树的贡献是啥，假设 x_i=a，那么我们枚举 [0,a] 中的值作为其儿子的权值，也即 \exp(a^Ax\int_0^af(t,x)\textrm{d}t)。

因为连向 n+1 的点权值是 y，所以答案

f(y,x)=\exp(y^Ax\int_0^y f(t,x) \textrm{d}t)

由此其实可以发现，f(y,x) 其实是一个关于 x,y 的二元生成函数。

更深一步，我们发现 f(y,x) 可以表示为 g(z)，其中 z=y^{A+1}x。

这个怎么得到呢，我不会理性证明（，但是感性理解，从 [x^0]f=1 开始，每次积分，指数加一，乘上前面的 y^Ax，就变成了 y^{A+1}x，重复该过程，应该可以归纳证明（？，反正可以感性理解。

好，这下可以设 g(z)=f(y,x)=\sum\limits_{i\ge0} g_i z^{i}，其中 z=y^{A+1}x，再设 h(z) 表示 \exp 里面的多项式，可以得到 h(z)=\sum\limits_{i\ge0}\dfrac{g_i}{(A+1)i+1}z^{i+1}，这东西咋得到的呢，考虑后面的积分式 t^{(A+1)i}x^i 在积一次过后变成 \dfrac{t^{(A+1)i+1}x^i}{(A+1)i+1}，对于上界，在乘上前面的项就变成 z^{i+1}，而且下界是 0，所以直接就消掉了，常数项 C 在 \exp 下必须是 0，所以就表示出 h 了。

而后 g=\exp h，直接 O(n^2) 递推即可。

提交记录。