题目链接:HDU-6574 Rng
题意
给出一个\(n(1\leq n \leq 10^6)\),生成一个区间的方法为:在\([1,n]\)中等概率随机生成一个\(R\),再在\([1,R]\)中等概率随机生成一个\(L\),\([L,R]\)就是生成的区间。用这样的方法生成两个区间,问这两个区间相交的概率。
思路
相交的概率不好求,将问题求两区间相交概率转换为(1 - 两区间不相交概率)。
两区间不相交即 \(min(R_1,R_2) < max(L_1, L_2)\),随机生成两个区间的过程可转换为随机生成两个数 a 和 b ,作为 \(min(R_1, R_2)\) 和 \(max(L_1, L_2)\),因为只要这两个确定了,另外的端点无论是多少都不影响线段是否相交。在 [1, n] 中生成两个数的总方案数为 \(n^2\)。
令两区间不相交的方案数为:
\[\sum_{a=1}^nn - a = \frac{n (n - 1)}{2} \]
则不相交概率为:\(\frac{n(n-1)}{2n^2} = \frac{n-1}{2n}\) 。
相交概率为:\(1-\frac{n-1}{2n}=\frac{n+1}{2n}\)。