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

· · 题解

感觉就是，不要一上来就套你所熟知的各种技巧，包括不限于：容斥，提前计算贡献，拆式子等。

先考虑 p_i=0 的 Subtask。这种只关心相邻两数的相对大小关系的题目，可以考虑插入 DP。具体的，我们只关心前缀的相对大小关系，并且只需要知道当前前缀最后一个数在这个前缀中的排名。记 dp_{i,j} 表示：a_i 在前 i 个数是第 j 大，前 i 个数所有相对大小关系对应的权值之和；转移通过枚举第 (i+1) 个数和第 i 个数的相对大小关系，容易进行前缀和优化 DP，复杂度 \mathcal O(n^2)（直接暴力可做到 \mathcal O(n^3)）。

对于一般的情况，主要问题在于：只记录相对大小关系是不够的！

如上图所示，设红色为，相对顺序中已经确定值的元素。我们是从左到右扫描的，因此左边的这个矩形中，这些元素某种程度上被限制住了：之后我们想把新的数插入到左边的这个矩形中，就有了一定的限制：相邻两个红球中的黑球个数必须是给定值。

直接记录相邻两个关键数中已经插入了多少个数是不现实的。但是，我们可以把这些数放回数轴上。记 v 表示当前最大的已知的数，那么我们可以记录 <v 的数中有多少个（c_1）没有被用上，然后新的数填在这 c_1 个数中。我们还要记录右边的信息，也就是当前用了多少个（c_2 个）大于 v 的数（这一步就比较像 CSP25T4 了）。不能忘记的，还有：当前最后一个数和我们记录的信息的相对大小关系。排除最后一个数是定值的情况，最后一个数只有两种大的情况：

直接记录 dp_{i,c_1,c_2,t} 表示：考虑了前 i 个数，有 c_1 个小于 \max_{1 \le j \le i} p_j 的数可用，以及 c_2 个大于 \max_{1 \le j \le i} p_j 的数还没有确定他们具体的值；上一个数和这 c_1+c_2 个数的相对大小关系是 t。

这样状态数看起来就已经是 \Theta(n^4) 的，实在太不牛了。一个直觉告诉我们，如果 c_1 很小，说明大部分数都用了 < \max_{1 \le j \le i}p_j 的值，也就是 c_2 也会很小。进一步分析后容易发现：两数之差 c_1-c_2 应该是一个只依赖 i 的常数，这样我们只需要记录 c_1，状态数降到 \Theta(n^3)。

然后考虑转移 i \to i+1。转移部分其实比较 easy，一些细节可以看我的代码，这里只简单描述一下。

  1. 如果下一个数未确定，那么可以根据它和上一个数的相对大小关系（以及 \max_{1 \le j \le i} p_j 的相对大小关系）进行分类讨论；
  2. 如果下一个数确定了，这时候涉及到最大值的扩展。 如上图所示，假设最大值 v_1 \to v_2，我们可以将 (k \le v_2-v_1-1) 个 > v_1 的数转化为 <v_2，有 \binom{v_2-v_1-1}{k} 种方法。根据 k，也可以确定它和上一个数的相对大小关系来计算系数。

对于第一种情况，我们发现：给定 (i,c_1,t)，对 (i+1) 的贡献形如 (i+1,c_1',[t'_l,t'_r])，那么可以使用差分，主动填写 (i+1) 的值；对于第二种情况，我们发现，贡献形如 (i,c_1,[t_l,t_r]) \to (i+1,c_1',c_1'+1)，那么对 i 数组关于 t 求前缀和即可。并且，对于每个有变化的 (i,c)，会计算 \Delta p_{\max} 次 k 的转移。不过 \sum \Delta p_{\max} = \mathcal O(n)，因此这部分的复杂度仍为 \mathcal O(n^3)。

在滚动数组的加持下，可以做到 \Theta(n^2) 空间，\mathcal O(n^3) 时间。可能是我太长时间没写代码了，感觉有一点卡常，就加了一下 Barret Reduction。

可读性（也许）比较高的代码

#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=500+10;
int n,MOD,p[MAXN],w[MAXN],C[MAXN][MAXN];
//left-right 个数保持一定 
ll dp[2][MAXN][MAXN];
struct Mod
{
    ll m, p;
    inline void init(const int pp) { m = ((__int128)1 << 64) / pp; p = pp; }
    inline ll operator ()(const ll x)
    {
        return x - ((__int128(x) * m) >> 64) * p;
    }
} mod;
inline void Add(const int st,const int left,const int l,const int r,const int v) {
    if(left<0||l>r||!v) return ;
    dp[st][left][l]+=v,dp[st][left][r+1]+=MOD-v;
    return ;
}
inline int Solve(void) {
    mod.init(MOD);
    memset(dp,0,sizeof(dp));
    C[0][0]=1; ffor(i,1,n) {C[i][0]=1;ffor(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;} 
    int delta=0,lstv=0; dp[0][0][1]=1,w[0]=1;
    ffor(i,1,n) {
        int st=(i&1),lst=st^1;
        ffor(c,0,n) ffor(t,0,n+1) dp[st][c][t]=0;
        if(p[i]) {
            //直接往右边推进，反而简单一些。选择右边的前 k 个放到左边去，注意更新 t'
            //如果 t<=left+1+k 那么会新增. 
            ffor(c,0,n) ffor(t,1,n+1) {
                dp[lst][c][t]+=dp[lst][c][t-1];
                if(dp[lst][c][t]>=MOD) dp[lst][c][t]-=MOD;
            }
            ffor(c,0,n) {
                int left=c,right=left-delta,len=p[i]-lstv-1;
                if(right<0||left+right>n) continue ;
                ffor(k,0,min(len,right)) {
                    ll add=mod(dp[lst][c][left+1+k]*(w[i-1]-1)+dp[lst][c][n+1]+MOD);
                    if(add) dp[st][left+len-k][left+len-k+1]+=mod(C[len][k]*add);
                }   
            }
            ffor(c,0,n) ffor(t,c+1,c+1) {
                dp[st][c][t]=mod(dp[st][c][t]);
                if(dp[st][c][t]>=MOD) dp[st][c][t]-=MOD;
            }
            delta+=p[i]-lstv-1,lstv=p[i];
        }
        else {
            ffor(c,0,n) ffor(t,1,n+1) if(dp[lst][c][t]) {
                int left=c,right=left-delta;
                if(right<0||left+right>n) continue ; 
                ll v=dp[lst][c][t];
                if(t<=left+1) {
                    if(i-1==0||p[i-1]) { //上一个数是确定的 
                        //case1 更小：left 减少，t'=1~left 
                        Add(st,left-1,1,left,v);
                        //case2 更大：left 不变，t'=left+2~left+right+2 
                        Add(st,left,left+2,left+right+2,mod(v*w[i-1]));
                    }
                    else {
                        //case 1 更小：left 减少，t'=1~t-1
                        Add(st,left-1,1,t-1,v);
                        //case 2.1 更大：left 减少，t'=t~left
                        ll mzx;
                        Add(st,left-1,t,left,mzx=mod(v*w[i-1]));
                        //case 2.2 更大：left 不变，t'=left+2~left+right+2    
                        Add(st,left,left+2,left+right+2,mzx);
                    }
                }
                else {
                    //case 1 更大：left 不变，t'= t+1~left+right+2
                    Add(st,left,t+1,left+right+2,mod(v*w[i-1]));
                    //case 2.1 更小：left 不变，t'=left+2~t
                    Add(st,left,left+2,t,v);
                    //case 2.2 更小：left 减小，t'=1~left 
                    Add(st,left-1,1,left,v);
                }
            }
            ffor(c,0,n) ffor(t,1,n+1) {
                if(dp[st][c][t]) {
                    dp[st][c][t]=mod(dp[st][c][t]+dp[st][c][t-1]);
                    if(dp[st][c][t]>=MOD) dp[st][c][t]-=MOD;
                }
                else dp[st][c][t]=dp[st][c][t-1];
            }
            delta--;
        }
    }
    int res=0;
    ffor(p,0,n+1) res=(res+dp[n&1][0][p])%MOD;
    return (res%MOD+MOD)%MOD;
}
int ascend(int C,int N,int M,vector<int> P,vector<int> W) {
    n=N,MOD=M;
    ffor(i,1,n) p[i]=P[i-1];
    ffor(i,1,n-1) w[i]=W[i-1];
    return Solve(); 
}

虽然这篇题解写得很长，但是核心思路很简单：先考虑最朴素的插入 DP，然后通过简单修正处理“存在定值”的情况，再经观察降低状态数，最后用前缀和优化转移。

个人感觉绝对难度并不比 CSP25T4 高多少，问题可能出在这是 APIO。