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

Watersphere · 2026-05-11 13:15:30 · 题解

好像并没有那么困难，这个做法感觉是中位紫。

众所周知，我们可以在 O(n^2) 的复杂度内算得 p_i=0 的答案，也就是使用 WC2026 所讲的欧拉数 DP 算法，于是考虑多加一维状态。

首先可以 n \leftarrow n+2，然后全部数字 +1 并在前后补上 1 和 n，可以少掉不少边界，设 rp_i 表示最小的 j \ge i 满足 p_j \not= 0。

不妨设状态 dp_{i,x,j} 表示前 i 个位置，<p_{rp_i} 有 x 个空位，在 i 填的数下面有 j 个空位，这里注意如果 j \le x 表示 p_i \le p_{rp_i}，否则 p_i > p_{rp_i}。

扫描 i=1 \dots n-1，对于每个 i 依次进行如下转移：

• p_i \not=0

  只有状态 dp_{i,x,x} 有用，并且可以得到 >p_i 的数的个数 y=i-p_i+x 以及距离下一个数的空格数量 len=p_{rp_{i+1}}-p_i-1，枚举 z \le \min(len,y)，有转移：f_{x+len-z,x} \leftarrow dp_{i,x,x} \binom{len}{z}，最后用临时的 f 数组覆写 dp_i 即可，这部分是在做 rp_i 到 rp_{i+1} 的转变。

• p_{i+1} \not=0

  直接模拟转移有：dp_{i+1,x,x} \leftarrow dp_{i,x,j} \times (1+(w_i-1)[j \le x])。

• p_{i+1}=0

  类似地可以得到 >p_i 的数的个数 y=i-p_i+x+1，有如下转移：

  dp_{i+1,x-1,k} \leftarrow dp_{i,x,j} \times (1+(w_i-1)[k \ge j]) & k \in [0,x-1] \\ dp_{i+1,x,k} \leftarrow dp_{i,x,j} \times (1+(w_i-1)[k > j]) & k \in [x+1,x+y+1]\\ \end{cases}

  显然可以前缀和优化到 O(n^3)。

于是就做完了，这个思路比较浅显直白，不需要太多的转化，也不需要逆元，组合数直接递推预处理即可，总复杂度 O(n^3)，代码长度不到 2k。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=500;
int rp[N+5],dp[N+5][N+5][N+5];
long long C[N+5][N+5],tmp[N+5][N+5];
int ascend(int c,int n,int mod,vector<int> p,vector<int> w){
    w.resize(n+2); for(int i=n;i>=2;i--) w[i]=w[i-2]; w[n+1]=w[1]=1;
    p.resize(n+3); for(int i=n+1;i>=2;i--) p[i]=p[i-2]; p[n+2]=n+2,p[1]=1; n+=2;
    for(int i=2;i<n;i++){if(p[i]) p[i]++;}
    for(int i=1;i<=n;i++){
        for(int x=0;x<=n;x++){
            for(int j=0;j<=n;j++) dp[i][x][j]=0;
        }
    }
    for(int i=0;i<=n;i++){
        C[i][0]=1; for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }dp[1][0][0]=1;
    for(int i=n;i>=1;i--) rp[i]=(p[i]? i:rp[i+1]);
    for(int i=1;i<n;i++){
        if(p[i]){
            for(int x=max(0,p[i]-i);x<min(n-i+1,p[i]);x++){
                int y=i-p[i]+x,len=p[rp[i+1]]-p[i]-1;
                for(int z=0;z<=min(len,y);z++) tmp[x+len-z][x]=(tmp[x+len-z][x]+C[len][z]*dp[i][x][x])%mod;
            }
            for(int x=0;x<p[rp[i+1]];x++){
                for(int j=0;j<=n;j++) dp[i][x][j]=tmp[x][j],tmp[x][j]=0;
            }
        }
        if(p[i+1]){
            for(int x=0;x<p[rp[i+1]];x++){
                for(int j=0;j<=x;j++) dp[i+1][x][x]=(1ll*dp[i][x][j]*w[i]+dp[i+1][x][x])%mod;
                for(int j=x+1;j<=n;j++) dp[i+1][x][x]=(dp[i+1][x][x]+dp[i][x][j])%mod;
            }
        }
        else{
            for(int x=max(0,p[rp[i+1]]-i-1);x<min(n-i,p[rp[i+1]]);x++){
                int y=i-p[rp[i+1]]+x+1,A,B;
                if(x){
                    tmp[x-1][0]+=1ll*dp[i][x][0]*w[i]%mod;
                    tmp[x-1][x]-=1ll*dp[i][x][0]*w[i]%mod;
                }
                for(int j=0;j<=x+y;j++){
                    if(!dp[i][x][j]) continue;
                    A=dp[i][x][j],B=1ll*dp[i][x][j]*w[i]%mod;
                    if(x&&j) tmp[x-1][0]+=A,tmp[x-1][x]-=B,tmp[x-1][min(x,j)]+=B-A;
                    tmp[x][x+1]+=A,tmp[x][x+y+2]-=B,tmp[x][max(x+1,j+1)]+=B-A;
                }
            }
            for(int x=max(0,p[rp[i+1]]-i-2);x<min(n-i,p[rp[i+1]]);x++){
                int y=i-p[rp[i+1]]+x+1; tmp[x][0]%=mod;
                for(int j=1;j<=x+y+2;j++) tmp[x][j]=(tmp[x][j]+tmp[x][j-1])%mod;
                for(int j=0;j<=x+y+1;j++) dp[i+1][x][j]=tmp[x][j],tmp[x][j]=0;
            }
        }
    }
    return (dp[n][0][0]+mod)%mod;
}