@codeforces - 1187F@ Expected Square Beauty

柔光的暖阳◎ 2023-06-01 13:59 10阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

给定一个序列 x = \{x1, x2, ..., xn\}，已知 xi 是一个在 \[li, ri\] 内的随机整数。

令 B(x) 表示将序列 x 划分成若干连续的段，使每个段内所有数相同的最小划分数。

求 (B(x))^2 的期望 E((B(x))^2)。

**Input**  
第一行包含一个整数 n (1≤n≤2⋅10^5))表示序列长度。  
第二行包含 n 个整数 l1,l2,…,ln (1≤li≤10^9)。  
第三行包含 n 个整数 r1,r2,...,rn (li≤ri≤10^9)。

**Output**  
输出 E((B(x))^2) 对 10^9 + 7 的取模结果。

**Examples**  
**Input**  
3  
1 1 1  
1 2 3  
**Output**  
166666673

**Input**  
3  
3 4 5  
4 5 6  
**Output**  
500000010

## @solution@ ##

平方期望看起来非常劝退，我们不妨从线性期望出发，考虑先计算 E(B(x))。  
注意到 B(x) 可以通过计算 “使得 x\[i\] 与 x\[i+1\] 不同的 i 的个数” + 1 得到，于是我们考虑每一个 i 对 E(B(x)) 的贡献。  
感性地认知一下，或许我们通过计算一对 (i, j) 对 E((B(x))^2) 的贡献？

考虑用期望的方法论证我们上面的想法。  
令 \\(I\_i(x)\\) 是一个随机变量，其中当 \\(x\[i\] = x\[i + 1\]\\) 时 \\(l\_i(x) = 0\\)，否则 \\(l\_i(x) = 1\\)。  
令 \\(P\_i(x)\\) 表示 \\(x\[i\]\\not=x\[i + 1\]\\) 的概率，则有 \\(E(l\_i(x)) = P\_i(x)\\)。

由于 \\(B(x) = \\sum\_\{i=1\}^\{n-1\}I\_i(x) + 1\\)，则 \\(E(B(x)) = E(\\sum\_\{i=1\}^\{n-1\}l\_i(x) + 1) = \\sum\_\{i=1\}^\{n-1\}E(l\_i(x)) + 1\\)。  
上式可以通过期望的线性性质得到，于是恰好印证了我们一开始的感性推导。

接下来考虑 \\(E(B(x)^2)\\)，可以得到如下式子：  
\\\[E(B(x)^2) = E((\\sum\_\{i=1\}^\{n-1\}l\_i(x) + 1)^2) = \\sum\_\{i=1\}^\{n-1\}E(l\_i(x)^2) + 1 + 2\*\\sum\_\{i=1\}^\{n-1\}(E(l\_i(x))+\\sum\_\{j=i+1\}^\{n-1\}E(l\_i(x)\*l\_j(x)))\\\]

考虑 \\(E(l\_i(x)\*l\_j(x))\\)，其实就是 i 和 j 同时发生的概率，所以可以立即得到 \\(E(l\_i(x)^2) = E(l\_i(x))\\)。  
又因为假如 \\(|i - j| > 1\\)，即 i, j 不相邻时，它们之间的概率是不会互相影响的。  
所以 \\(E(l\_i(x)\*l\_j(x)) = P\_i(x)\*P\_j(x) = E(l\_i(x))\*E(l\_j(x))\\)，当 \\(|i - j| > 1\\) 时。

我们不妨令 \\(Q\_i(x) = E(l\_i(x)\*l\_\{i+1\}(x))\\)。通过以上这些推导，我们可以把式子进一步化简：  
\\\[E(B(x)^2) = 3\*\\sum\_\{i=1\}^\{n-1\}P\_i(x) + 1 + 2\*\\sum\_\{i=1\}^\{n-1\}P\_i(x)(\\sum\_\{j=i+2\}^\{n-1\}P\_j(x)) + 2\*\\sum\_\{i=1\}^\{n-2\}Q\_i(x)\\\]

现在考虑怎么求 P 和 Q。

首先是 \\(P\_i(x)\\)，即 i 和 i+1 不相同的概率。考虑容斥，即用 1 - 相同的概率。  
相同的时候一定是从 i 的区间与 i+1 的区间的交中选择一个数，于是相同的概率 = 区间交的长度 / i 的区间长度 / i+1 的区间长度。

然后是 \\(Q\_i(x)\\)，一样考虑容斥，求 1 - (i 与 i + 1 相同的概率) - (i + 1 与 i + 2 相同的概率) + (i, i + 1 与 i + 2 相同的概率)。  
三个相同的概率可以类比两两相同的概率得到，一样是求区间交。

## @accepted code@ ##

#include<cstdio> #include<algorithm> using namespace std; const int MAXN = 200000; const int MOD = int(1E9) + 7; int pow_mod(int b, int p) { int ret = 1; while( p ) { if( p & 1 ) ret = 1LL*ret*b%MOD; b = 1LL*b*b%MOD; p >>= 1; } return ret; } int P[MAXN + 5], S[MAXN + 5]; int l[MAXN + 5], r[MAXN + 5], n; 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]); for(int i=1;i<n;i++) { int len = max(0, min(r[i], r[i + 1]) - max(l[i], l[i + 1]) + 1); int tmp = 1LL*pow_mod(r[i] - l[i] + 1, MOD - 2)*pow_mod(r[i + 1] - l[i + 1] + 1, MOD - 2)%MOD; P[i] = (1 + MOD - 1LL*tmp*len%MOD)%MOD; } for(int i=1;i<n;i++) S[i] = (P[i] + S[i-1])%MOD; int ans = (3LL*S[n - 1]%MOD + 1)%MOD; for(int i=1;i+2<n;i++) ans = (ans + 2LL*(S[n - 1] + MOD - S[i + 1])%MOD*P[i]%MOD)%MOD; for(int i=1;i+1<n;i++) { int len = max(0, min(r[i], min(r[i + 1], r[i + 2])) - max(l[i], max(l[i + 1], l[i + 2])) + 1); int tmp = 1LL*pow_mod(r[i] - l[i] + 1, MOD - 2)%MOD*pow_mod(r[i + 1] - l[i + 1] + 1, MOD - 2)%MOD*pow_mod(r[i + 2] - l[i + 2] + 1, MOD - 2)%MOD; int del = 1; del = ((del + P[i])%MOD + MOD - 1)%MOD; del = ((del + P[i + 1])%MOD + MOD - 1)%MOD; del = (del + 1LL*tmp*len%MOD)%MOD; ans = (ans + 2LL*del%MOD)%MOD; } printf("%d\n", ans); }

## @details@ ##

其实有一个简化公式的方法，即令 \\(l\_n(x) = 1\\)，将上面 1 全部替换成 \\(l\_n(x)\\)。

其他应该就没什么了。代码也比较好写。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11401521.html