题意
有 \(n\) 个实数，第 \(i\) 个实数在 \([0, 2 ^ {a_i}]\) 中均匀分布。求任意一个数均小于 \(n\) 个数和的一半的概率。
\(n \le 5 \cdot 10 ^ 4, a_i \le 50\)。
解法
题目即求 \(\sum\limits_{i = 1}^{n} P(x_i > \sum\limits_{j \neq i} x_j)\)，由于 \(x_i\) 和 \(2^{a_i} - x_i\) 分布相同，即求 \(\sum\limits_{i =1}^{n} P(\sum\limits_{j=1}^{n} x_j < 2 ^ {a_i})\)。
拆分成整数部分和小数部分，可以看成每个数随机 \([0,2 ^ {a_i})\) 的整数和 \([0,1)\) 的小数。
小数部分
\(n\) 个 \([0, k]\) 均匀分布的实数的和不超过 \(k\) 的概率：\(P(\sum\limits_{i=1}^{n} x_i \le k) = \dfrac{k^n}{n!}\)，可以先积分 \(n - 1\) 层，再逐个求出最后一层的值。
容斥，钦定有 \(i\) 个数超过了 \(1\)，则答案为 \(\sum\limits_{i=0}^{n}(-1)^i \dbinom{n}{i} \dfrac{(k-i)^n}{n!}\)。
整数部分
相当于每个数的每个二进制位随机。
设 \(f(i, j)\) 表示考虑了从低到高的前 \(i\) 位，当前进位 \(j\) 的概率。
设 \(g(i, j)\) 表示当前位有 \(j\) 次进位的概率，卷积即可。
答案即为 \(f(a_i-1, 0)\)。
标签：le,limits,实数,sum,赛题,概率,模拟,小数 From： https://www.cnblogs.com/Aria-Math/p/18433504