2019 年的尾巴在 2021 年的钟声即将敲响之际被解决了！

我的肯定不是最快的，但一定是很短的。

没看懂其他人在干什么干脆自己瞎推了。

考虑令 \(pos\) 表示全局最高点（如果有多个，就选最右边的那个），容易发现 \([1,pos-1]\) 的点都无法移动到 \(pos\) 后面，\([pos+1,n]\) 的点都无法移动到 \(pos\) 前面，这下两边就变成了互不影响的区间。可以想到以此来区间 DP 。

令 \(dp_{l,r}(x)\) 表示区间 \([l,r]\) 最大值为 \(x\) 时的方案数，转移的时候枚举一下最大值可能的位置转移即可，注意用前缀和优化。

这下子的话复杂度是 \(O(n^2m)\) 的，其中 \(m\) 为权值最大值，不可接受。考虑到一个区间内可能转移的最大值只有 \(O(1)\) 个，可能的区间数或许远没有 \(n^2\) 。打表可以发现 \(n\leq 300\) 时区间数是 \(2518\) ，这样就可以通过 \(50\) 分了。

void solve(int l,int r) {
    if(vis[l][r]) return ;
    int now=++tot; vis[l][r]=now;

    if(l>r) dp[now][0]=1;
    else {
        lep(i,l,r) if(abs(i-l-r+i)<=2) {
            solve(l,i-1),solve(i+1,r);
            lep(j,a[i],b[i]) pls(dp[now][j],mul(dp[vis[l][i-1]][j],dp[vis[i+1][r]][j-1]));
        }
    }
    lep(j,1,m) pls(dp[now][j],dp[now][j-1]);
}

接下来一档分是 \(a=1,b=10^9\) 的。不妨思考一下，这档 \(a,b\) 均一样的分意义何在？

首先将 \(a,b\) 集体减一。可以发现当 \(l=r\) 的时候，\(dp_{l,r}(x)\) 多项式的最高项是 \(x^{0}\) ，其前缀和的多项式最高项是 \(x^{1}\) 。当两边合并的时候，继续观察，不难发现 \(dp_{l,r}(x)\) 的前缀和是 \(r-l+1\) 次多项式。

我们的目标是 \(dp_{1,n}(m)\) ，直接拉插即可。

满分做法？容易发现比如说 \(a_i=3,b_i=5\) 时，\(dp_{i,i}(x)\) 的最高项并不是 \(x^{0}\) ，称这种情况为"不满足条件"。但是如果将值域段定为 \([3,5]\) ，就没问题了。而且可以发现，如果定义一段值域 \([3,4]\) 以及一段值域 \([5,5]\) ，那么 \(dp_{i,i}(x)\) ，对于第一段值域满足条件，对于第二段值域仍然满足条件（显然前面值域段做前缀和后对于当且值域段都是常数项）。

回忆 APIO2016 划艇，对于每个 \([a_i,b_i]\) 将其拆分为若干个左闭右开的区间 \([c_t,c_{t+1})\) ，容易发现处理后只有 \(O(n)\) 个左闭右开的区间。

这样逐段 DP 即可。每一段 DP 只需要 DP \([c_t,c_{t}+n-1]\) 这段区间，然后就可以拉插了。具体地，对每个 DP 状态的前缀和都拉插求出其在 \(c_{t+1}-1\) 时的取值后继续做下一段即可。

因为拉插时下标连续，所以可以线性拉插，因此拉插一次时间复杂度 \(O(n)\) 。每一轮一共有 \(m\leq2518\) 个状态需要拉插，一共有 \(O(n)\) 轮（\(O(n)\) 段左闭右开的区间），因此时间复杂度是 \(O(n^2m)\) 的，实现精细可以通过。

不知道为什么 UOJ 上 T 成 95 了。

// {{{ solve

bool vis[N][N];
int L,T,tot,id[N][N],dp[S][N];

void init(int l,int r) {
    if(id[l][r]) return ; id[l][r]=++tot;
    if(l<=r) lep(i,l,r) if(abs(i-l-r+i)<=2) init(l,i-1),init(i+1,r);
}
void solve(int l,int r) {
    if(vis[l][r]) return ; vis[l][r]=true;
    if(l>r) dp[id[l][r]][0]=1;
    else {lep(i,l,r) if(abs(i-l-r+i)<=2&&(a[i]<=T&&T<b[i])) {
        solve(l,i-1),solve(i+1,r);
        lep(j,1,L) pls(dp[id[l][r]][j],mul(dp[id[l][i-1]][j],dp[id[i+1][r]][j-1]));
    }}
    lep(j,1,L) pls(dp[id[l][r]][j],dp[id[l][r]][j-1]);
}

// }}}

int tmp[N],invfac[N]; inline void lagrange(const int l,const int r) {
    if(n+l>=r) {lep(t,1,tot) dp[t][0]=dp[t][r-l+1]; return ;}
    tmp[n+1]=1; rep(i,n,1) tmp[i]=mul(tmp[i+1],r-i-l);
    lep(t,1,tot) dp[t][0]=0;

    int qwq=1; lep(i,l,l+n) {
        int res=mul(mul(tmp[i-l+1],qwq),mul(
            ((l-n+i)&1)?mod-invfac[l+n-i]:invfac[l+n-i],invfac[i-l]));
        lep(t,1,tot) pls(dp[t][0],mul(res,dp[t][i-l+1]));
        qwq=mul(qwq,r-i);
    }
}

int c[N<<1]; int main() {
    scanf("%d",&n);
    lep(i,1,n) scanf("%d%d",&a[i],&b[i]),c[++m]=a[i],c[++m]=++b[i];
    std::sort(c+1,c+1+m),m=std::unique(c+1,c+1+m)-c-1;
    lep(i,1,n)
        a[i]=std::lower_bound(c+1,c+1+m,a[i])-c,
        b[i]=std::lower_bound(c+1,c+1+m,b[i])-c;

    invfac[0]=1;
    lep(i,1,n+3) invfac[i]=mul(invfac[i-1],i);
    invfac[n+3]=modpow(invfac[n+3],mod-2);
    rep(i,n+3,1) invfac[i-1]=mul(invfac[i],i);

    init(1,n); for(T=1;T<m;++T) {
        L=min(c[T+1]-c[T],n+1),memset(vis,0,sizeof(vis));
        lep(l,1,n) lep(r,1,n) if(id[l][r]) solve(l,r);
        lagrange(c[T],c[T+1]-1);
        lep(t,1,tot) lep(i,1,L) dp[t][i]=0;
    }
    printf("%d\n",dp[vis[1][n]][0]);
    return 0;
}