这里是一道逆元的练习题
RNG
Problem Description
Avin is studying how to synthesize data. Given an integer $n$, he constructs an interval using the following method: he first generates a integer $r$ between $1$ and $n$ (both inclusive) uniform-randomly, and then generates another integer $l$ between $1$ and $r$ (both inclusive) uniform-randomly. The interval $ [ l , r ] $ is then constructed. Avin has constructed two intervals using the method above. He asks you what the probability that two intervals intersect is. You should print $p \times q^{−1} (\% 1, 000, 000, 007)$, while $\frac{p}{q}$ denoting the probability.
Input
Just one line contains the number n (1 ≤ n ≤ 1, 000, 000).
Output
Print the answer.
Sample Input
1
2
Sample Output
1
750000006
题目大意是在长度为 $ 0 $ ~ $ n $ 的数轴上随机的选择一段，然后再随机选择另外一段（这两段线段的选取完全随机，互不影响），线段的端点只会位于整数点上，求两段线段相交的概率是多少。
首先看到题目可以想到容斥原理：
相交的概率=1-不相交的概率
那么现在我们要求的是不相交的概率
对于一段线段而言，有两个端点——左端点和右端点，假设第一段线段的两个端点是$l_1,r_1$第二段线段的两个端点是$l_2,r_2$
我们按照题目先选一段再选一段就有两种情况（按照端点分情况）
第一种就是选取的$r_1$在$r_2$的左边
则两线段不相交的概率为$\frac{r_2-r_1}{r_2}$
第二种就是选取的$r_1$在$r_2$的右边
则两线段不相交的概率为$\frac{r_1-r_2}{r_1}$
则在$r_1$固定时，枚举$r_2$可得
设
则$r_1$不固定时，有
化简到最后有
这是不相交的概率计算，相交的概率为
处理一个后缀和就可以$O(n)$求解了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using namespace std;
const int mod = 1e9 + 7;
long long qk(long long a, long long n) {
long long res = 1;
while (n) {
if (n & 1)res = res * a % mod;
n >>= 1;
a = a * a % mod;
}
return res;
}
long long las[1004];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
las[i] = qk(i, mod - 2);
}
for (int i = n - 1; i >= 1; --i) {
las[i] = (las[i] + las[i + 1]) % mod;
}
long long ans = 0;
las[n + 1] = 0;
for (int i = 1; i <= n; ++i) {
ans = (ans + (1 + i) * qk(2, mod - 2) % mod) % mod;
ans = (ans + i * (las[i + 1]) % mod) % mod;
}
cout << ans * qk(n, mod - 2) % mod * qk(n, mod - 2) % mod << endl;
}
P.S. 最后有人~推出~（或者猜出）究极公式是$\frac{n+1}{2n}$
那么放一下YJW的代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
using namespace std;
const int mod = 1e9 + 7;
long long ksm(long long a, long long b){
long long ans = 1;
while(b){
if(b & 1)
ans = (ans * a) % mod;
b >>= 1;
a = (a * a) % mod;
}
return ans % mod;
}
int main() {
int n;
while(cin>> n){
cout<< ((n + 1) * ksm(2 * n, mod - 2)) % mod<< endl;
}
return 0;
}