题解 P3643 【[APIO2016]划艇】

· · 题解

同步更新于我的博客：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;
}