CF1187F Expected Square Beauty

给定一个整数数组 $x = [x_1, x_2, \dots, x_n]$。我们定义 $B(x)$ 为将 $x$ 划分为若干个子段，使得每个子段内所有元素都相等的最小划分数。例如，$B([3, 3, 6, 1, 6, 6, 6]) = 4$，一种划分方式为 $[3, 3\ |\ 6\ |\ 1\ |\ 6, 6, 6]$。 现在你并不知道 $x$ 的具体数值，但你知道 $x_i$ 可以是区间 $[l_i, r_i]$ 内的任意整数（$l_i \le r_i$），且每个 $x_i$ 独立且等概率地取值。 请计算 $(B(x))^2$ 的期望值，即 $E((B(x))^2)$。保证该期望值可以表示为最简分数 $\frac{P}{Q}$，请输出 $P \cdot Q^{-1} \bmod 10^9 + 7$。

第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示数组 $x$ 的长度。 第二行包含 $n$ 个整数 $l_1, l_2, \dots, l_n$（$1 \le l_i \le 10^9$）。 第三行包含 $n$ 个整数 $r_1, r_2, \dots, r_n$（$l_i \le r_i \le 10^9$）。

输出一个整数，表示 $E((B(x))^2)$，即 $P \cdot Q^{-1} \bmod 10^9 + 7$。

以下是第一个样例所有可能的 $x$ 取值： - $[1, 1, 1]$：$B(x) = 1$，$B^2(x) = 1$； - $[1, 1, 2]$：$B(x) = 2$，$B^2(x) = 4$； - $[1, 1, 3]$：$B(x) = 2$，$B^2(x) = 4$； - $[1, 2, 1]$：$B(x) = 3$，$B^2(x) = 9$； - $[1, 2, 2]$：$B(x) = 2$，$B^2(x) = 4$； - $[1, 2, 3]$：$B(x) = 3$，$B^2(x) = 9$； 所以 $E = \frac{1}{6} (1 + 4 + 4 + 9 + 4 + 9) = \frac{31}{6}$，即 $31 \cdot 6^{-1} = 166666673$。 第二个样例所有可能的 $x$ 取值： - $[3, 4, 5]$：$B(x) = 3$，$B^2(x) = 9$； - $[3, 4, 6]$：$B(x) = 3$，$B^2(x) = 9$； - $[3, 5, 5]$：$B(x) = 2$，$B^2(x) = 4$； - $[3, 5, 6]$：$B(x) = 3$，$B^2(x) = 9$； - $[4, 4, 5]$：$B(x) = 2$，$B^2(x) = 4$； - $[4, 4, 6]$：$B(x) = 2$，$B^2(x) = 4$； - $[4, 5, 5]$：$B(x) = 2$，$B^2(x) = 4$； - $[4, 5, 6]$：$B(x) = 3$，$B^2(x) = 9$； 所以 $E = \frac{1}{8} (9 + 9 + 4 + 9 + 4 + 4 + 4 + 9) = \frac{52}{8}$，即 $13 \cdot 2^{-1} = 500000010$。 由 ChatGPT 4.1 翻译