自动搬运

查看原文

来自洛谷，原作者为

	sky_of_war **

搬运于2025-08-24 21:51:07，当前版本为作者最后更新于2019-05-06 13:10:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

同步更新于我的博客：APIO2016划艇

Solution

首先有一种比较好想的状态表示：$f_{i, j}$为前$i$所学校中，第$i$所学校参赛，且派出$j$艘划艇的方案数。这样的话最后答案就是$\displaystyle \sum_i \sum_j f_{i,j}$，转移大概就是：

$$\begin{aligned}f_{0,1} &= 1\\f_{i, j} &=\begin{cases}\displaystyle \sum_{k=1}^{j-1}\sum_{p=0}^{i-1}f_{p, k}, &j\in I_i\\0, &j \notin I_i\end{cases}\end{aligned} $$

这种状态表示有一个很严重的问题在于，第二维的范围是$10^9$的，连$9$分都过不去。 对于这种范围比较大的数据，可以考虑离散化。 重新定义设一下状态：先把区间离散化成$\mathcal O(n)$个端点，然后设$f_{i, j}$为前$i$所学校中，第$i$所学校参赛，且派出的划艇数落到第$j$个区间内的方案数。于是在第$i$所学校之前的学校便分为了两类：在区间$j$内的和不在区间$j$内的。 考虑怎么计算在区间$j$内的贡献。先来证明一个引理。

Lemma. 从区间$[0,L]$中取$n$个数，要求所有非零数严格递增，则方案数为$\binom{L+n}{n}$。

Proof. 对于没有$0$的情况，答案肯定就是$\binom L n$。原因是如果我们确定了一种组合，那么方案也就随之确定了，就是这个组合的从小到大的排列，这两者一一对应。对于把$0$加进去的情况，观察如下序列：

$$\underbrace{\text{0 0 0 $\dots$ 0}}_{n \text{个} } \text{ 1 2 3 $\dots L$} $$

考虑从这个序列取$n$个数，方案数为$\binom{L+ n}{n}$。可以发现，它和原问题的答案是一一对应的！取第$i$个$0$对应着第$i$次取$0$，取某个非零数$k$对应着没取$0$的第$k$次取$k$。于是我们就通过这个巧妙的构造轻而易举地证明了该引理。$\square$

回到原来的问题，由于第$i$所学校必须参赛，所以计算的时候$0$的个数需要$-1$。方案数即为$\binom{m+L-1}m$，$m$表示挑选划艇个数包含第$j$个区间的学校的数量。具体来说就是枚举上一个有学校的区间$k$，前$p$所学校不在区间$j$中，则$m$是$p+1..i$号学校中能选区间$j$的学校的数量，则转移方程容易得出，即：

$$\begin{aligned}f_{0,1}&=1\\f_{i, j} &= \begin{cases}\displaystyle\sum_{k=1}^{j-1}\sum_{p=0}^{i-1}\binom{L+m-1}m f_{p, k}, &j\subseteq I_i (\text{记为}\square \text{式})\\0, &j \nsubseteq I_i\end{cases}\end{aligned} $$

这东西显然可以前缀和处理。设

$$g_{i, j} = \sum_{k=1}^{j-1}f_{i, k}$$

于是$(\square)$可以简化为

$$f_{i, j} = \sum_{p=0}^{i-1}\binom{L+m-1}mg_{p, j-1}, j \subseteq I_i $$

关于实现，每次递推好组合数防止过多的取模就可以了。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
constexpr int MAXN = 5e2 + 10;
typedef long long ll;
constexpr int mo = 1e9 + 7;
using namespace std;
int n, tot, a[MAXN], b[MAXN], num[MAXN << 1], g[MAXN], C[MAXN], inv[MAXN];
template <class T>
inline void _read(T &x)
{
    x = 0;
    char t = getchar();
    while(!isdigit(t)) t = getchar();
    while(isdigit(t))
    {
        x = x * 10 + t - '0';
        t = getchar();
    }
}
template <class T>
inline void print(T x)
{
    if(x < 0)
    {
        putchar('-');
        x = -x;
    }
    if(x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}
template <class T>
inline int fastmod(T x)
{
    if (x >= mo) return x - mo; else return x;
}
int main()
{
    _read(n);
    inv[1] = 1;
    for(int i = 2; i <= n; ++i) inv[i] = (ll)(mo - mo / i) * inv[mo % i] % mo;
    for(int i = 1; i <= n; ++i)
    {
        _read(a[i]), _read(b[i]);
        num[++tot] = a[i];
        num[++tot] = b[i] + 1;
    }
    sort(num + 1, num + 1 + tot);
    tot = unique(num + 1, num + 1 + tot) - num - 1;
    for(int i = 1; i <= n; ++i)
    {
        a[i] = lower_bound(num + 1, num + 1 + tot, a[i]) - num;
        b[i] = lower_bound(num + 1, num + 1 + tot, b[i] + 1) - num;
    }
    C[0] = 1;
    g[0] = 1;
    for(int j = 1; j < tot; ++j)
    {
        int len = num[j + 1] - num[j];
        for(int i = 1; i <= n; ++i) C[i] = (ll)C[i - 1] * (len + i - 1) % mo * inv[i] % mo;
        for(int i = n; i; --i)
            if(a[i] <= j && j + 1 <= b[i])
            {
                int f = 0, m = 1, c = len;
                for(int p = i - 1; p >= 0; --p)
                {
                    f = fastmod(f + (ll)c * g[p] % mo);
                    if(a[p] <= j && j + 1 <= b[p]) c = C[++m];
                }
                g[i] = (g[i] + f) % mo;
            }
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i) ans = fastmod(ans + g[i]);
    print(ans);
    return 0;
}