题解：P16433 [APIO 2026 中国赛区] 上升

· · 题解

赛场上 2.5h 过了这道题（最终收获铜牌），乱写的 n^3。

首先考虑 p_i=0 的 DP，实际上这个有一点像 CSP T4，我们设 dp_{i,j} 表示填了前 i 个数，上一个位置是已经填了的数中第 j 个数，转移是容易的，就你枚举当前位置填第几个位置转移即可。

然后考虑拓展这个写法，我们发现如果它给定了这个 p_i 我们就无法判断这一个位置应该是第几个，因为可能和前面的发生冲突（就是有些段已经填满了，你无法往里面加数）。

我们记 lst_i 表示上一个 p_i 有值的位置，如果我们想填小于等于 lst_i 的值实际上由于 p_i 是单调的，我们只需要知道它有多少个空位即可，所以考虑加一维记录这个，这样我们第二维就可以表示它填在那个空位后面，否则如果是记录的填的个数，想通过枚举当前这一位填在某个填过的后面，这个是有可能填不了的。

但是对于想填大于 lst_i 的值，我们如果记录空位，我们到下一个 p_i 有值的位置，并不知道哪些空位应该小于 p_i，所以大于 lst_i 的值还是记录它是填过的数中第几个。

所以就有一个状态 dp_{i,j,k,0/1} 表示填了前 i 个位置，有 j 个值小于等于 lst_i，0/1 表示上一个填的是否大于等于 lst_i，填的是第 k 个空位后（0 的情况），还是第 k 个已填的数（1 的情况）。

这个转移是比较容易的，时间复杂度是 O(n^4)，使用前缀和优化可以得到 O(n^3)。

有些许卡常。

Code

#include<bits/stdc++.h>
#define ll int
#define fi first
#define se second
#define pii pair<int,int>
#define ls(x) ((x)*2)
#define rs(x) ((x)*2+1)
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i,  b) for(int i=1,i##end=b;i<=i##end;i++)
using namespace std;
const int N=1e6+5;
ll p[N],w[N],Mod;
ll lst[N],pre[N];
ll dp[2][505][505][2],qzh[505][505][2];
ll C[505][505]; 
#define Add(x,y) (x+y>=Mod?x+=y-Mod:x+=y)
#define work(j,l,r,c,w) ((l<=r)?(Add(qzh[j][l][c],w),Add(qzh[j][r+1][c],Mod-w),vis[j]=1):0)
bool vis[N];
int ascend(int c, int n, int MM, std::vector<int> P, std::vector<int> W){

    P.push_back(n+1);Mod=MM;
    C[0][0]=1;
    For(i,1,500){
        C[i][0]=1;
        For(j,1,i) (C[i][j]=(C[i-1][j-1]+C[i-1][j]))%=Mod;
    }
    For(i,1,n+1)p[i]=P[i-1];
    For(i,1,n-1)w[i]=W[i-1];
    For(i,1,n){
        if(p[i]) lst[i]=p[i];
        else lst[i]=lst[i-1];
    }
    For(j,0,n)For(t,0,n)For(c,0,1)For(i,0,1)dp[i][j][t][c]=0;
    if(p[1]) dp[1][p[1]-1][p[1]-1][0]=1;
    else dp[1][0][1][1]=1;
    For(i,1,n) pre[i]=pre[i-1]+(p[i]>0);
    For(i,2,n){
        For(j,0,lst[i])For(t,0,n)For(c,0,1)dp[i&1][j][t][c]=qzh[j][t][c]=0; 
        if(!p[i]){
            For(t,0,n) vis[t]=0;
            //0
            For(j,0,lst[i-1])For(t,0,n)if(n-lst[i-1]>=i-1-(lst[i-1]-j)&&dp[(i-1)&1][j][t][0]){
                work(j-1,0,t-1,0,dp[(i-1)&1][j][t][0]);
                work(j-1,t,j-1,0,1ll*dp[(i-1)&1][j][t][0]*w[i-1]%Mod);
                work(j,lst[i-1]-j+1,i,1,1ll*dp[(i-1)&1][j][t][0]*w[i-1]%Mod);
            }
            //1
            For(j,0,lst[i-1])For(t,0,n)if(n-lst[i-1]>=i-1-(lst[i-1]-j)&&dp[(i-1)&1][j][t][1]){
                work(j-1,0,j-1,0,dp[(i-1)&1][j][t][1]);
                work(j,lst[i-1]-j+1,t,1,dp[(i-1)&1][j][t][1]);
                work(j,t+1,i,1,1ll*dp[(i-1)&1][j][t][1]*w[i-1]%Mod);
            }
            For(j,0,lst[i])if(vis[j])For(t,1,n)For(c,0,1)Add(qzh[j][t][c],qzh[j][t-1][c]);
            For(j,0,lst[i])if(vis[j])For(t,0,n)For(c,0,1)Add(dp[i&1][j][t][c],qzh[j][t][c]);
        }
        else{
            int mid=lst[i]-lst[i-1]-1;
            For(j,0,lst[i-1])For(t,0,n)if(n-lst[i-1]>=i-1-(lst[i-1]-j)&&dp[(i-1)&1][j][t][0]){
                For(k,0,min(mid,i-1-(lst[i-1]-j))){
                    Add(dp[i&1][j+mid-k][j+mid-k][0],1ll*dp[(i-1)&1][j][t][0]*w[i-1]%Mod*C[mid][k]%Mod);
                }
            }
            For(j,0,lst[i-1])For(t,0,n) if(n-lst[i-1]>=i-1-(lst[i-1]-j)&&dp[(i-1)&1][j][t][1]){
                For(k,0,min(mid,i-1-(lst[i-1]-j))){
                    if(t<lst[i]-(j+mid-k))Add(dp[i&1][j+mid-k][j+mid-k][0],1ll*dp[(i-1)&1][j][t][1]*w[i-1]%Mod*C[mid][k]%Mod);
                    else Add(dp[i&1][j+mid-k][j+(mid-k)][0],1ll*dp[(i-1)&1][j][t][1]*C[mid][k]%Mod);
                }
            }
        }
//          For(j,0,lst[i])For(t,0,n)For(c,0,1) if(dp[i&1][j][t][c])cout<<i<<" "<<j<<" "<<t<<" "<<c<<" "<<dp[i&1][j][t][c]<<endl;
    }
    int ans=0;
    For(t,0,n)For(c,0,1) ans+=dp[n&1][0][t][c],ans%=Mod;
    return ans;
}