【题解】「NOI2019」机器人 区间 DP + 拉格朗日插值 — Qiuly

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;
}