hdu6574 Rng（概率）

题意：

给定n，按照以下方法生成区间：先在[1,n]中随机选择一个R，然后在[1,R]中等概率随机生成一个L， 那么生成的区间为[L,R]。

按照以上方法随机生成两个区间，问这两个区间相交的概率。

答案对1e9+7取模。

数据范围：n<=1e6

解法：

1.考虑计算不相交的概率

$题目的先R再L是没有很大作用的，改成先L再R也一样，$

$其实就是随机选择一个区间，$

$那么我们可以将取两个区间的问题变为：$

$1.第一个区间先取一个R1，再取一个L1$

$2.第二个区间先取一个L2，再取一个R2$

$想要令两个区间不相交，那么要让R1<L2$

$方案数为{\sum }_{R1=1}^n{\sum }_{L1=R1+1}^{n}1$

$=n\ast (n-1)/2$

$上面只考虑了R1和L2，没有考虑L1和R2是因为它们不影响相交性$

$任意选取R1和L2的方案数为n^2$

$那么不相交的概率为\frac{n\ast (n-1)/2}{n^2}=\frac{n-1}{2n}$

$则相交的概率为1-\frac{n-1}{2n}=\frac{n+1}{2n}$

ps： 感觉有点玄学

参考： https://www.cnblogs.com/kangkang-/p/12902071.html

2.考虑直接计算相交的概率

这个好像好想一点，懒得写了，鸽了

code1：

#include<bits/stdc++.h> using namespace std; #define ll long long int ppow(int a,int b,int mod){ int ans=1%mod;a%=mod; for(;b;a=1ll*a*a%mod,b>>=1)if(b&1)ans=1ll*ans*a%mod; return ans; } const int maxm=2e5+5; const int mod=1e9+7; signed main(){ ll n; while(cin>>n){ ll ans=(n+1)*ppow(2*n,mod-2,mod)%mod; cout<<ans<<endl; } return 0; }

---