Codeforces 1187F Expected Square Beauty
题目链接
https://codeforces.com/contest/1187/problem/F
题目大意
一个长度为 $n$ 的数列 $x$ ，每个位置上等概率出现 $L_i$ 到 $r_i$ 之间的数。设 $B(x)$ 为该数列的连续相同数字子段的个数，求 $E((B(x))^2)$。
题目分析
设 $f(i) = [x_i \neq x_{i – 1}]$ ，则有 $B(x) = \sum\limits_{i=1}^{n}f(i)$， 则有 $E((B(x))^2) = E((\sum\limits_{i=1}^{n}f(i))^2)$
将内层展开，则有 $E((B(x))^2) = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}{E(f(i)f(j))}$
考虑计算 $E(f(i)f(j))$ ，则会出现三种情况。
-
$|i – j| > 1$，那么显然 $f(i)$ 于 $f(j)$ 之间互不影响，答案显然为 $E(f(i))E(f(j))$
-
$i = j$ ，显然 $f(i)$ 和 $f(j)$ 要么同时发生，要么同时不发生，因此答案显然为 $E(f(i))$
-
$|i – j| = 1$，那么显然他们之间会互相影响，那么需要求的是 $[x_i \neq x_{x – 1} \& x_j \neq x_{j – 1}]$。
显然 $1$ 和 $2$ 中的可以直接用 $1$ 减去 $x_i = x_{i – 1}$ 的概率求出，而 $3$ 中的使用容斥也同样很容易求出来。
最后将这些求和即可得到答案。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
int n;
long long L[maxn];
long long R[maxn];
long long p[maxn];
long long qpow(long long b, long long x){
long long ret = 1;
while(x){
if(x & 1){
ret = ret * b % mod;
}
x >>= 1;
b = b * b % mod;
}
return ret;
}
int main(){
int i, j;
long long ans = 0;
long long sum = 0;
scanf("%d", &n);
for(i=1;i<=n;i++){
scanf("%lld", &L[i]);
}
for(i=1;i<=n;i++){
scanf("%lld", &R[i]);
}
for(i=1;i<=n;i++){
p[i] = (mod + 1 - max(0ll, min(R[i], R[i - 1]) - max(L[i], L[i - 1]) + 1) * qpow((R[i] - L[i] + 1) * (R[i - 1] - L[i - 1] + 1) % mod, mod - 2) % mod) % mod;
ans = (ans - p[i] * p[i] + p[i]) % mod;
ans = (ans + mod) % mod;
sum += p[i];
}
sum %= mod;
ans = (ans + sum * sum) % mod;
for(i=2;i<=n;i++){
ans = (ans - 2ll * p[i] * p[i - 1] % mod + mod) % mod;
long long x = 1 - (1 - p[i]) - (1 - p[i - 1]) + max(0ll, min(min(R[i], R[i - 1]), R[i - 2]) - max(max(L[i], L[i - 1]), L[i - 2]) + 1)
* qpow((R[i] - L[i] + 1) * (R[i - 1] - L[i - 1] + 1) % mod * (R[i - 2] - L[i - 2] + 1) % mod, mod - 2) % mod;
ans += 2ll * x;
ans %= mod;
}
printf("%lld\n", (ans + mod) % mod);
return 0;
}