题解：序列期望

题目传送门
外网传送门

好，正片开始。

1. 期望的处理

根据代码源集训告诉我们， $\mathbb E=\frac{\text{总数}}{\text{方案数}}$，证明如下。

$$\mathbb E=P \times \text{收益}=\frac{1}{方案数} \times \text{总数}=\frac{\text{总数}}{\text{方案数}}$$

那么我们知道，方案数为 $∏_{i=1}^n r_i-l_i+1$，那么问题是如何求总数。

2. 总数

第一阶段，错误的尝试

我们考虑对于每个数的贡献，不难想到枚举 $h$，再看看在那个数取最大值，那么对于每一个数，就可以很轻松求出贡献，即

$$\sum_{i=\max\{h - r_i, 0\} + 1}^{h-l_i+1} i$$

为什么呢，我真的觉得很显然。

当 h <= r[i] 时

a[i]: ______l_____h__r
           最大   最小
并且取值连续。=> 等差数列求和

当 h > r[i] 时

a[i]:  ______l________r___h__
            max      min
并且取值连续。=> 等差数列求和

那么我们可以发现，这个公式与那个数取到最大值无关，所以我们可以去掉枚举最大值那一层循环，对于每一个数，都算一遍那个公式。最后看那个点取最大值，就不算那个点。这时，但是这却存在一个隐性错误。

第二阶段，去重

那么，我们发现，当有多个数取最大值时，这种情况会被多算，怎么办呢？

很显然，我们枚举最大值点时只考虑所有等于最大值的数中最右边的那个，例如：当 我取 3 3 1 3 2 时，我只在枚举到最后一个 3 时有贡献。

那么我们维护一个贡献前缀积与一个后缀积，前缀积包括最大值，后缀积不包含取到最大值，最后乘起来，总和呼之欲出。

如何计算不包含最大值，eh，其实就是当 $h \le r_i$ 时减一个 $1$.

那么，最后不要忘了除以方案数哦！！！

可恶的蠕虫，我连题都看不到。

这么复杂的方法还有6个赞（angry）!

思路

我们根据期望的定义，有

$$\text{期望}=\sum\text{概率}\cdot\text{价值}=\sum\frac{1}{\text{总方案数}}\cdot\text{价值}=\frac{1}{\text{总方案数}}\cdot\sum\text{价值}=\frac{\text{总价值}}{\text{总方案数}}$$

总方案数是简单的(题目甚至都告诉你了)，为 $\prod_{i=1}^n r_i-l_i+1$，难点在于求总价值。

考虑固定最大值 $h$，对于每个变量 $x_i$，它对答案的贡献是 $h-x_i+1$。

答案就是 $\sum (h-x_{i,1}+1)(h-x_{i,2}+1)(h-x_{i,3}+1)\cdots$

这个怎么求呢？

先考虑简单情况：

$$x_1\text{ }x_2\text{ }x_3\\y_1\text{ }y_2\\z_1\text{ }z_2$$

在 $x$ 中选一个、$y$ 中选一个、$z$ 中选一个，相乘再求和，这个东西我们会这样算：

$$ans=\\x_1y_1z_1+x_1y_1z_2+x_1y_2z_1+x_1y_2z_2+\\ x_2y_1z_1+x_2y_1z_2+x_2y_2z_1+x_2y_2z_2+\\ x_3y_1z_1+x_3y_1z_2+x_3y_2z_1+x_3y_2z_2$$

然后再乘法分配律一下，

$$ans=x_1y_1z_1+x_1y_1z_2+\cdots+x_3y_2z_2\\=(x_1+x_2+x_3)(y_1+y_2)(z_1+z_2)$$

我们记 $f(h)$ 表示 $\forall x_i\leq h$ 的答案，根据刚才的公式，

$$f(h)=\prod_{i=1}^n\sum_{x_i=l_i}^{\min(r_i,h)}(h-x_i+1)$$

$\sum_{x_i=l_i}^{\min(r_i,h)}(h-x_i+1)$ 是可以通过等差数列求和 $\Theta(1)$ 求的，所以我们可以在 $\Theta(n)$ 求出 $f(h)$，那我们再容斥一下就可以求出最大值恰好为 $h$ 时的答案，为 $f(h)-f(h-1)$，即去掉 $\forall x_i<h$ 的答案

代码

复杂度：外层枚举 $h$，里面 $\Theta(2n)$ 求出 $f(h)$ 和 $f(h-1)$，总时间复杂度为 $\Theta((maxr-maxl)\cdot n)$。

• st 和 ed 分别表示 $h$ 的最小值和最大值，显然 $st=\max_{i=1}^n l_i$ (因为 $max_{i=1}^n x$ 至少这么多)，$ed=\max_{i=1}^n r_i$ (因为 $max_{i=1}^n x$ 至多这么多)；

• now 表示 $x\leq h$ 的价值总和 pre 表示 $x\leq h-1$ 的价值总和；

• calc 表示 $\sum_{i=l}^r h-x+1$ 的值。

// sequence
#include <iostream>
using namespace std;

const int MOD = 1e9 + 7;
int n, l[1005], r[1005], sum, cnt = 1, st, ed;

int quick_pow(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1) res = 1ll * res * x % MOD;
        x = 1ll * x * x % MOD;
        y >>= 1;
    }
    return res;
}

int calc(int l, int r, int h) { // sum of (h - x + 1), x in [l, r]
    int sum_x = 1ll * (l + r) * (r - l + 1) / 2ll % MOD;
    return (1ll * (r - l + 1) * (h + 1) % MOD - sum_x + MOD) % MOD;
}

int main() {
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &l[i], &r[i]);
        cnt = 1ll * cnt * (r[i] - l[i] + 1) % MOD;
        st = max(st, l[i]);
        ed = max(ed, r[i]);
    }
    for (int h = st; h <= ed; ++h) {
        int now = 1, pre = 1;
        for (int i = 1; i <= n; ++i) {
            now = 1ll * now * calc(l[i], min(r[i], h), h) % MOD;
            pre = 1ll * pre * calc(l[i], min(r[i], h - 1), h) % MOD;
        }
        sum = (sum + (now - pre + MOD) % MOD) % MOD;
    }
    int ans = 1ll * sum * quick_pow(cnt, MOD - 2) % MOD;
    printf("%d\n", ans);
    return 0;
}