SS241119C. 甜果（sugar）

题意

有 \(n\) 个人，每个人初始有 \(a_i\) 颗糖果，有 \(n\) 个事件，事件 \(i\) 是如果 \(a_i > a_{b_i}\)，那么 \(a_i' : = a_i + w_i\)。

问所有事件以随机的排列的顺序依次发生后，每个人的期望糖果数量。

思路

即求每个事发生的概率 \(p_i\)，那么 \(ans_i = a_i + p_i w_i\)。

考虑什么时候 \(p_i\) 会发生，什么时候不会发生。

设 \(t_i\) 表示操作 \(i\) 发生的时间。

• 当 \(a_i \le a_{b_i}\) 时，\(p_i = 0\)。
• 当 \(a_i > a_{b_i}+w_{b_i}\) 时，\(p_i=1\)。
• 当 \(a_{b_i} < a_i \le a_{b_i}+w_i\) 时，如果 \(p_{b_i} =1 且 t_{b_i} < t_i\)，\(p_i=0\)，否则 \(p_i = 1\)。

这启发我们对于第三种情况，从 \(i\) 向 \(b_i\) 连边。这样我们就会连出若干条链。而每个 \(p_i\) 只和与它同一条链的点，进一步地，只和链上在它后面的那些点是否发生有关。

对于一条链，上面的点 \(x_0\)，我们扔掉在它前面的那些点，使 \(x_0\) 成为链头，后面依次是 \(x_1 \sim x_{len-1}\)。

如果 \(t_{x_{j+1}} > t_{x_j}\)，那么 \(p_{x_j}=0\)，因此我们枚举最小的 \(j\)，满足 \(t_{x_{j+1}} > t_{x_j}\)，那么有 \(p_{x_j}=0\)，那么 \(x_{j+1} \sim x_{len-1}\) 的 \(p\) 是多少，对 \(p_{x_0}\) 都没有影响了。

因此有 \(t_{x_0} > t_{x_1} > \cdots > t_{x_j} < t_{x_{j+1}}\)。

当 \(j\) 是奇数的时候 \(p_{x_0}=1\)，满足 \(t_{x_0 \sim x_j}\) 降序的方案数是 \(\frac{n!}{(j+1)!}\)，这个方案还需要减去不满足 \(t_{x_j} < t_{x_j+1}\) 的情况，即 \(\frac{n!}{(j+2)!}\)。

因此 \(p_{x_0} = \frac{1}{n!}\sum_{j=1}^{len} (-1)^j \frac{n!}{j!} = \sum_{j=1}^{len} \frac{(-1)^j}{j!}\)。

这个长成错排公式的样子。可以递推预处理错排公式，然后对每个 \(x_0\) 求概率。时间复杂度 \(O(n)\)。