题解

思路

记 $Y_i=[x_i\ne x_{i+1}]$，则 $B=1+\sum Y_i$。展开平方：

$$\mathbb E(B^2)=1+3\sum_i\mathbb E(Y_i)+2\sum_{i<j}\mathbb E(Y_iY_j).$$

两个区间各自长度为 $d_i,d_{i+1}$，交集整数个数为 $c$ 时，

$$p_i=\Pr(Y_i=1)=1-\frac{c}{d_id_{i+1}}.$$

当 $j>i+1$ 时，$Y_i,Y_j$ 涉及互不相交的随机变量，所以独立，联合概率为 $p_ip_j$。只有相邻两条边需要修正。容斥得到

$$q_i=\Pr(Y_i=1,Y_{i+1}=1) =1-\Pr(x_i=x_{i+1})-\Pr(x_{i+1}=x_{i+2}) +\Pr(x_i=x_{i+1}=x_{i+2}).$$

最后一项等于三个区间的交集长度除以三个区间长度之积。

做法

先线性求出所有 $p_i$。维护已经出现的 $p$ 之和即可累计所有 $p_ip_j$；再对每对相邻边加上 $q_i-p_ip_{i+1}$ 的修正。所有除法均乘以模逆元完成。

子任务 1 可枚举所有可能数组；子任务 2 可显式枚举所有边对，非相邻边相乘、相邻边用三元交集计算。

复杂度

时间复杂度为 $O(n\log MOD)$（每个区间求一次快速幂逆元），空间复杂度为 $O(n)$。