Harsh Comments
这题有两种思考方式。
方式一：min-max 容斥
设小 X 的物品中，第 \(i\) 个物品在时间 \(t_i\) 被拿走，于是答案是 \(E(\max\limits_{i\in T} t_i)\)，其中 \(T=\{1,2,\cdots,n\}\)。
注意以下用第 \(n+1\sim n+m\) 个物品表示小 Y 的物品，设 \(H=\{n+1,n+2,\cdots,n+m\}\)。
考虑 min-max 容斥，
\[E(\max_{i\in T} t_i)=\sum_{S\subseteq T,S\neq\emptyset} (-1)^{|S|+1} E(\min_{i\in S} t_i)
\]
设随机变量 \(x_i\) 表示 \(i\) 是否在 \(S\) 任意元素被删之前 先删去，\(x_i\in\{0,1\}\)，要求 \(i\notin S,\)，那么根据期望的线性性，有
\[\begin{aligned}
\text{原式} &= \sum_{S\subseteq T,S\neq\emptyset} (-1)^{|S|+1} \left(1+\sum_{i\in T \setminus S}E(x_i)+\sum_{i\in H} E(x_i)\right) \\
&= \sum_{S\subseteq T,S\neq\emptyset} (-1)^{|S|+1} \left(1+\sum_{i\in T \setminus S}P(x_i=1)+\sum_{i\in H} P(x_i=1)\right) \\
& \left( \text{下面补证：}P(x_i=1)=\frac{a_i}{a_i+sum(S)}, sum(S)=\sum_{i\in S} a_i \right) \\
&= \sum_{S\subseteq T,S\neq\emptyset} (-1)^{|S|+1} \left(1+\sum_{i\in T \setminus S}\frac{a_i}{a_i+sum(S)}+\sum_{i\in H} \frac{a_i}{a_i+sum(S)}\right)
\end{aligned}
\]
括号里分成了 \(3\) 部分，最后一部分可以对 \(T\) 做背包求得，不要忘了算上容斥系数。这部分复杂度为 \(O(n\cdot sum + m\cdot sum\log M)\)，\(M\) 为模数。
最前面部分用二项式定理可知等于 \(1\)。
考虑化简中间部分，
\[\begin{aligned}
\sum_{S\subseteq T,S\neq\emptyset} (-1)^{|S|+1} \sum_{i\in T \setminus S}\frac{a_i}{a_i+sum(S)} &= \sum_{S\subseteq T,|S|\ge 2} (-1)^{|S|}\sum_{i\in S}\frac{a_i}{sum(S)} \\
&= \sum_{S\subseteq T,|S|\ge 2} (-1)^{|S|} \\
&= \sum_{i=2}^{n} (-1)^i \binom{n}{i} \\
&= n-1
\end{aligned}
\]
于是最后答案为 \(n\)，加上前面背包那部分算的答案。
方式二
首先也是根据期望的线性性，把 \(E(cnt)\) 拆成 \(n+m\) 个随机变量期望之和，\(cnt\) 为最后删去的物品数。
可以发现物品 \(1\sim n\) 对应的随机变量一定 \(=1\)，因为最后一定会删去它们，所以对答案的贡献是 \(n\)。
考虑物品 \(n+1\sim n+m\)，对答案的贡献就是 \(P(x_i=1)\)，即：物品 \(i\) 在小 X 的物品删完之前，被删去的概率。
直接算不好算，我们考虑容斥，那么
\[P(x_i=1)=\sum_{S\in T,S\neq\emptyset} (-1)^{|S|+1} \frac{a_i}{a_i+sum(S)}
\]
也就是枚举 \(T\) 的子集，钦定它们在物品 \(i\) 之后删去，
于是总答案为：
\[n+\sum\limits_{i\in H} P(x_i=1)=n+\sum_{i\in H}\sum_{S\in T,S\neq\emptyset} (-1)^{|S|+1} \frac{a_i}{a_i+sum(S)}
\]
后面部分一样用背包求。
小优化
模拟赛题目 \(n,m\le 500\)，带上求逆元的 \(O(\log M)\) 会超时。
但发现 \(\sum a_i<10^9+7\)，于是我们可以线性递推出 \(1\sim 5\times 10^7\) 的逆元，然后由于 \(a_i>5\times 10^7\) 的物品有 \(20\) 个左右，因此用快速幂的次数不会太多。
补证
给定 \(n\) 个小球，重量为 \(a_i\)，假设箱子里剩余小球总重量是 \(sum\)，那么从中抽取出小球 \(j\) 的概率是 \(j/sum\)，现在进行 \(n\) 次不放回的抽取，证明：小球 \(i\) 在小球 \(j\) 之前取出的概率是 \(a_i/(a_i+a_j)\)。
我们对 \(n\) 归纳。
当 \(n=2\) 时显然成立。
当 \(n>2\) 时，记全集为 \(T\)，答案为：
\[\begin{aligned}
&= \frac{a_i}{sum(T)}+\sum_{k\in T\setminus\{i,j\}}\frac{a_k}{sum(T)}\cdot\frac{a_i}{a_i+a_j} & \text{根据归纳假设} \\
&= \frac{a_i}{sum(T)}+\frac{sum(T)-a_i-a_j}{sum(T)}\cdot\frac{a_i}{a_i+a_j} \\
&= \frac{a_i}{sum(T)}(1+\frac{sum(T)-a_i-a_j}{a_i+a_j}) \\
&= \frac{a_i}{a_i+a_j}
\end{aligned}
\]
代码
Code
