【Codeforces1187F】Expected Square Beauty

发表于
https://codeforces.com/contest/1187/problem/F

题目链接：

【Codeforces1187F】Expected Square Beauty

题目描述：

有一个长度为 $ n $ 的数列，第 $ i $ 个数的取值范围为 $ [l_i, r_i] $ ，定义一个数列的价值为这个数列极长连续相同段的个数，求一个数列价值的平方期望，对 $ 10^9 + 7 $ 取模 。
$ n \leq 200000 $ 。

做法：

定义 $ F(x) $ 为数列的价值， $ I_i(x) $ 为数列中第 $ i $ 项与第 $ i - 1 $ 项是否不同 $ (I_i(x) = [x_i \neq x_{i - 1}]) $ ，则有 $ F(x) = \sum_{i = 1}^{n} I_i(x) $ 。
$$ E(B(x)^2) = E(\sum_{i = 1}^{n}I_i(x)\sum_{j = 1}^{n}I_j(x))\ = E(\sum_{i = 1}^{n}\sum_{j = 1}^{n}I_i(x)I_j(x))\ = \sum_{i = 1}^{n}\sum_{j = 1}^{n}E(I_i(x)I_j(x)) $$
考虑计算 $ 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 $ 时，仅考虑 $ j = i + 1 $ 的贡献（ $ i = j + 1 $ 同理）。$ E(I_i(x)I_j(x)) = P(x_{i - 1} \neq x_i \&\& x_i \neq x_{i + 1}) $ 。考虑容斥， $ E(I_i(x)I_j(x)) = 1 - p_i - p_{i + 1} + P(x_{i - 1} = x_i \&\& x_i = x_{i + 1}) $ ，就可以计算了。 

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 200010;
int n, l[N], r[N], inv[N], ans;
int e[N], pre[N], suf[N];

inline int add(const int &x, const int &y) {
	return x + y < mod ? x + y : x + y - mod;
}
inline int sub(const int &x, const int &y) {
	return x - y < 0 ? x - y + mod : x - y;
}
inline int mul(const int &x, const int &y) { return (int)((ll)x * y % mod); }
int ksm(int x, int y = mod - 2) {
	int ss = 1; for(; y; y >>= 1, x = mul(x, x)) if(y & 1) ss = mul(ss, x);
	return ss;
}
int calc(int x, int y, int z) {
	if(!x) return 0;
	int w = min(min(r[y], r[x]), r[z]) - max(max(l[y], l[x]), l[z]) + 1;
	if(w < 0) w = 0;
	int val = mul(mul(inv[x], inv[y]), inv[z]); return mul(w, val);
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &l[i]);
	for(int i = 1; i <= n; i++) scanf("%d", &r[i]);
	e[1] = 1, inv[1] = ksm(r[1] - l[1] + 1);
	for(int i = 2; i <= n; i++) {
		inv[i] = ksm(r[i] - l[i] + 1);
		e[i] = min(r[i], r[i - 1]) - max(l[i], l[i - 1]) + 1;
		if(e[i] < 0) e[i] = 0;
		e[i] = mul(e[i], mul(inv[i - 1], inv[i])), e[i] = sub(1, e[i]);
	}
	for(int i = 1; i <= n; i++) pre[i] = add(pre[i - 1], e[i]);
	for(int i = n; i >= 1; i--) suf[i] = add(suf[i + 1], e[i]);
	for(int i = 1; i <= n; i++) {
		if(i < n) ans = add(ans, mul(e[i], suf[i + 2]));
		if(i > 1) ans = add(ans, mul(e[i], pre[i - 2]));
	}
	for(int i = 1; i <= n; i++) ans = add(ans, e[i]);
	for(int i = 1; i < n; i++) {
		int sum = sub(1, add(sub(1, e[i + 1]), sub(1, e[i])));
		sum = add(sum, calc(i - 1, i, i + 1));
		ans = add(ans, add(sum, sum));
	}
	printf("%d\n", ans);
	return 0;
}