第一次做到这种类似代数方法运用期望性质的题的说
期望性质：
- 对于两个独立的对象 $A, B$，则有 $E (AB) = E(A)E(B)$
- 线性性：对于对象 $X, Y$，存在 $E(aX + bY) = aE(x) + bE(Y)$
首先设计函数 $I_i(x) = \begin{cases} 1 x_i \neq x_{i - 1} \ 0 x_i = x_{i - 1} \end{cases} (i > 1), ~ I_1(x) = 1$，则有 $B(x) = \sum\limits_{i = 1}^n I_i(x)$，故
$$
\begin{aligned}
E (B^2(x)) &= E (\sum\limits_{i = 1}^n I_i(x)\sum\limits_{j = 1}^n I_j(x)) \\
&= E (\sum\limits_{i = 1}^n\sum\limits_{j = 1}^n I_i(x)I_j(x)) \\
&= \sum\limits_{i = 1}^n\sum\limits_{j = 1}^n E(I_i(x)I_j(x))
\end{aligned}
$$
易知，若 $x_i = x_{i - 1}$ 的概率 $p_i = \frac{\min(r_{i - 1}, r_i) - \max (l_{i - 1}, l_i) + 1}{(r_{i - 1} - l_{i - 1} + 1)(r_i - l_i + 1)}$，那么 $x_i \neq x_{i - 1}$ 的概率，即 $E(I_i(x)) = 1 - p_i$，特别地，$p_1 = 0, E(I_1(x)) = 1$
那么此时对 $E (I_i(x)I_j(x))$ 进行讨论：
若 $i = j$，则 $E(I_i(x)I_j(x)) = E(I_i(x))$
若 $|i - j| > 1$，那么 $I_i(x)$ 与 $I_j(x)$ 分别独立，故 $E(I_i(x)I_j(x)) = E(I_i(x))E(I_j(x))$
若 $|i - j| = 1$，令 $i + 1 = j$，那么进行容斥，即 $E(I_i(x)I_{i- 1}(x)) = 1 - p_{i - 1} - p_i + P ((x_{i - 2} == x_{i - 1}) \bigcup (x_{i - 1} == x_i))$，根据 $E(I_i(x))$ 的计算方法，易知，$P ((x_{i - 2} = x_{i - 1}) \bigcup (x_{i - 1} = x_i)) = \frac{\min(r_{i - 2}, r_{i - 1}, r_i) - \max (l_{i - 2}, l_{i - 1}, l_i) + 1}{(r_{i - 2} - l_{i - 2} + 1)(r_{i - 1} - l_{i - 1} + 1)(r_i - l_i + 1)}$，特别地，$E(I_1(x)I_2(x)) = E(I_2(x))$
综上，最后答案为
$E(B^2(x)) = \sum\limits_{i = 1}^n(p_i + \sum\limits_{|i - j| > 1} p_j) + 2\sum\limits_{i = 2}^n E(I_i(x)I_{i - 1}(x))$
代码
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| #include <iostream>
#include <cstdio>
#include <cstring>
#define MOD 1000000007
using namespace std;
typedef long long LL;
const int MAXN = 2e05 + 10;
LL power (LL x, int p) {
LL cnt = 1;
while (p) {
if (p & 1)
cnt = cnt * x % MOD;
x = x * x % MOD;
p >>= 1;
}
return cnt;
}
int N;
int l[MAXN], r[MAXN];
int size[MAXN]= {0};
LL p[MAXN]= {0};
LL psum[MAXN]= {0};
int getnum () {
int num = 0;
char ch = getchar ();
while (! isdigit (ch))
ch = getchar ();
while (isdigit (ch))
num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
return num;
}
int main () {
N = getnum ();
for (int i = 1; i <= N; i ++) l[i] = getnum ();
for (int i = 1; i <= N; i ++) r[i] = getnum ();
for (int i = 1; i <= N; i ++) size[i] = r[i] - l[i] + 1;
for (int i = 2; i <= N; i ++) {
LL nume = max (0, min (r[i - 1], r[i]) - max (l[i - 1], l[i]) + 1);
LL base = 1ll * size[i - 1] * size[i] % MOD;
p[i] = nume * power (base, MOD - 2) % MOD;
}
for (int i = 1; i <= N; i ++)
psum[i] = (psum[i - 1] + (1ll - p[i] + MOD) % MOD) % MOD;
LL ans = 0;
for (int i = 1; i <= N; i ++) ans = (ans + (1ll - p[i] + MOD) % MOD) % MOD;
for (int i = 1; i <= N; i ++) {
if (i - 2 >= 1) ans = (ans + (1ll - p[i] + MOD) % MOD * psum[i - 2] % MOD) % MOD;
if (i + 2 <= N)
ans = (ans + (1ll - p[i] + MOD) % MOD * ((psum[N] - psum[i + 1] + MOD) % MOD) % MOD) % MOD;
}
LL part3 = 0;
if (N > 1) part3 = (1ll - p[2] + MOD) % MOD;
for (int i = 3; i <= N; i ++) {
LL nume = max (0, min (r[i - 2], min (r[i - 1], r[i])) - max (l[i - 2], max (l[i - 1], l[i])) + 1);
LL base = 1ll * size[i - 2] * size[i - 1] % MOD * size[i] % MOD;
LL per = ((1ll - p[i - 1] - p[i] + nume * power (base, MOD - 2) % MOD) % MOD + MOD) % MOD;
part3 = (part3 + per) % MOD;
}
part3 = part3 * 2ll % MOD;
ans = (ans + part3) % MOD;
cout << ans << endl;
return 0;
}
|
