【Codeforces1187F】Expected Square Beauty

发表于 更新于 本文字数： 3k 阅读时长 ≈ 3 分钟
https://codeforces.com/contest/1187/problem/F

题目链接：

【Codeforces1187F】Expected Square Beauty

题目描述：

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

n≤200000 n \leq 200000 。

做法：

定义 F(x) F(x) 为数列的价值， Ii(x) I_i(x) 为数列中第 i i 项与第 i−1 i - 1 项是否不同 (Ii(x)=[xi≠xi−1]) (I_i(x) = [x_i \neq x_{i - 1}]) ，则有 F(x)=∑i=1nIi(x) F(x) = \sum_{i = 1}^{n} I_i(x) 。

E(B(x)2)=E(∑i=1nIi(x)∑j=1nIj(x))=E(∑i=1n∑j=1nIi(x)Ij(x))=∑i=1n∑j=1nE(Ii(x)Ij(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(Ii(x)Ij(x)) E(I_i(x)I_j(x)) ，分三种情况考虑。
当 i=j i = j 时， E(Ii(x)Ij(x))=E(Ii(x)) E(I_i(x)I_j(x)) = E(I_i(x)) 。
当 ∣i−j∣>1 | i - j | > 1 时， Ii(x),Ij(x) I_i(x), I_j(x) 互不影响， E(Ii(x)Ij(x))=E(Ii(x))E(Ij(x)) E(I_i(x)I_j(x)) = E(I_i(x))E(I_j(x)) 。
当 ∣i−j∣=1 | i - j | = 1 时，仅考虑 j=i+1 j = i + 1 的贡献（ i=j+1 i = j + 1 同理）。E(Ii(x)Ij(x))=P(xi−1≠xi&&xi≠xi+1) E(I_i(x)I_j(x)) = P(x_{i - 1} \neq x_i \&\& x_i \neq x_{i + 1}) 。考虑容斥， E(Ii(x)Ij(x))=1−pi−pi+1+P(xi−1=xi&&xi=xi+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;
}