题解：P16416 【MX-X28-T5】「FAOI-R12」单人旅行

· · 题解

考虑 t 序列合法判定。记未填入的最小值为 m，则只要 c\ne m，就会把 m 填上，否则必然是在延伸 m 之后的一段值域连续段。考虑将值域按此划分，对一个划分段 [l,r]，其先依次填入了 (l,r] 再填入了 l，代表的 p 区间中前 r-l 个 c 均为 l 且最后一个 c\ne l。

考虑对此 DP。首先所有划分段的贡献容易 O(n^2) 预处理，p 上的相关限制实际上只有各划分段的最后一不定项不好处理，容易考虑贡献延后计算。定义 f(i,j) 为值域上划分段填满 [1,i] 且有 j 个待定位置的权值和，发现瓶颈在于 c\ne l 的限制。考虑钦定若干段满足 c=l。计钦定段数为 k，则容斥系数为 (-1)^k，直接分于每个钦定段转移时贡献 -1 的系数即可。

DP 转移直接枚举段长即可，因为段长不超过 c=l 的点数，因此枚举段长部分整体是 O(n) 的。值域上最后一段可以不填 l，故而需要枚举最后一个填满的段的位置，最后一段满足 c=l 容易处理。

void MAIN(){
    // #define MultiTasks
    const int N=5005;
    sto int n;read(n);
    sto int c[N],cnt[N];rep(i,1,n)read(c[i]),++cnt[chmin(c[i],n+1)];
    sto mint a[N],b[N];rep(i,1,n)read(a[i]);rep(i,1,n)read(b[i]);
    sto mint v[N][N],tv[N][N];rep(l,1,n){
        v[l][l]=a[l]*l+b[l],tv[l][l]=a[l]*(l+1)+b[l];
        rep(r,l+1,n)
            v[l][r]=tv[l][r-1]*(a[r]*l+b[r]),
            tv[l][r]=tv[l][r-1]*(a[r]*(r+1)+b[r]);
    }tv[n+1][n]=1;
    sto mint fc[N],iv[N];
    fc[0]=1;rep(i,1,n)fc[i]=fc[i-1]*i;
    iv[n]=1/fc[n];per(i,n,1)iv[i-1]=iv[i]*i;
    #define A(n,m) (fc[n]*iv[(n)-(m)])
    sto mint f[N][N];f[0][0]=1;
    repl(i,0,n)rep(j,0,i)if(f[i][j].x)rep(k,1,cnt[i+1]+1){
        if(i+k>n)break;
        f[i+k][j+1]+=f[i][j]*A(cnt[i+1],k-1)*v[i+1][i+k];
        if(k<=cnt[i+1])f[i+k][j]-=f[i][j]*A(cnt[i+1],k)*v[i+1][i+k];
    }
    mint ans;
    rep(i,0,n)rep(j,0,i)if(f[i][j].x&&cnt[i+1]>=n-i)ans+=f[i][j]*A(cnt[i+1],n-i)*fc[j]*tv[i+1][n];
    put(ans);
}