Luogu

LOJ

分析

一个显然的想法是设 $dp_{i,j}$ 表示前 $i$ 个学校，第 $i$ 个学校派了 $j(j\neq 0)$ 艘划艇的方案数，然而第二维高达 $10^9$。

可以想到把所有端点离散化一下（这里改成左闭右开区间会方便一些），$dp_{i,j}$ 的定义改为前 $i$ 个学校，第 $i$ 个学校派的划艇数在第 $j$ 个区间中的方案数。

考虑转移。我们枚举一个 $k$，然后让 $[k+1,i]$ 中的学校派的划艇数都在第 $j$ 个区间中。设 $[k+1,i]$ 中能派的划艇数与第 $j$ 个区间有交的学校数为 $x$，第 $j$ 个区间长度为 $len$，则我们要求 $x$ 个数放在 $[0,len]$ 中，$0$ 可以重复选、非 $0$ 数不能重复选的、最后一个数必须非 $0$ 的方案数，不难知道等于 $len+x-1\choose x$。于是有状态转移方程
$$
dp_{i,j}=\sum_{k=1}^{i-1}\sum_{p=0}^{i-1}{len+x-1\choose x}dp_{p,k}
$$
前缀和优化一下即可做到 $\mathcal{O}(n^3)$。

代码

写的时候最好把 $j$ 一维的循环丢到外面去，不然可能会 TLE。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500+10;
const int mod=1e9+7;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,l[N],r[N];
int S[N<<1],top=0;
int C[N],dp[N][N<<1],s[N][N<<1];

int main() {
    n=read();
    for (int i=1;i<=n;++i) {
        l[i]=read(),S[++top]=l[i];
        r[i]=read(),S[++top]=r[i]+1;
    }
    sort(S+1,S+top+1); top=unique(S+1,S+top+1)-S-1;
    for (int i=1;i<=n;++i) {
        l[i]=lower_bound(S+1,S+top+1,l[i])-S;
        r[i]=lower_bound(S+1,S+top+1,r[i]+1)-S;
    }
    for (int i=0;i<top;++i) s[0][i]=1;
    for (int j=1;j<top;++j) {
        int len=S[j+1]-S[j];
        for (int i=C[0]=1;i<=n;++i)
            C[i]=1ll*C[i-1]*(len+i-1)%mod*qpow(i,mod-2)%mod;
        for (int i=1;i<=n;++i) {
            if (l[i]<=j&&j+1<=r[i]) {
                for (int k=i-1,x=1;~k;--k) {
                    dp[i][j]=(dp[i][j]+1ll*s[k][j-1]*C[x])%mod;
                    if (l[k]<=j&&j+1<=r[k]) ++x;
                }
            }
            s[i][j]=(s[i][j-1]+dp[i][j])%mod;
        }
    }
    int ans=0;
    for (int i=1;i<=n;++i) ans=(ans+s[i][top-1])%mod;
    printf("%d\n",ans);
    return 0;
}