题解：P16433 [APIO 2026 中国赛区] 上升
george0929
·
·
题解
死于贡献延迟计算。
令 p_0=0,p_{n+1}=n+1。
先考虑 A 性质，按位 DP 记录当前值排名，可以做到 O(n^3) 或 O(n^2)。
考虑有 p 的限制怎么做，照样从前往后 DP，记 i 前最后一个有值的 p 为 p_x，关心 \leq p_x 的数和 >p_x 的数，\leq p_x 的绝对大小是关键的，使用预定 DP，>p_x 部分使用插入 DP，f_{i,j,k} 表示 [1,i]，有 j 个 \leq p_x 的数没有被使用，当前数字 \leq p_x，有 k 个没有被使用的数字小于当前数字；g_{i,j,k} 表示当前数字 >p_x，在 >p_x 的数字中排名为 k。
当 p_{i+1}=0 时，直接前缀和优化即可，具体的：
-
-
-
-
g\to f$：$g_{i,j,k}\to f_{i+1,j-1,k'}(k'\in [0,j-1])
当 p_{i+1}\neq 0 时，贡献延迟计算，先要求当前数字必须 >p_{x}，进行普通转移得到 g'_{i}，记 p_{i+1} 在 >p_x 中排名为 rk，将 rk-1 个 >p_x 的数字填入 (p_{x},p_{i+1}) 中，只需进行 g'\to f 的转移，g'_{i,j,rk}\to f_{i+1,j+p_{i+1}-p_x-rk,j+p_{i+1}-p_x-rk}，系数乘上 \binom{p_{i+1}-p_x-1}{rk-1}。
```cpp
#include<bits/stdc++.h>
using namespace std;
int mod;
void upd(int &x,int y){
x+=y;
if(x>=mod) x-=mod;
}
int C[505][505];
int f[2][505][505],g[2][505][505];
int n,a[505],w[505];
void DP(){
memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
f[1][0][0]=1;
for(int i=1;i<n;i++){
int px=0;
for(int j=i;j>=0;j--){
if(a[j]){
px=a[j];
break;
}
}
int now=i&1,nxt=!(i&1);
memset(f[nxt],0,sizeof(f[nxt]));
memset(g[nxt],0,sizeof(g[nxt]));
for(int j=0;j<px;j++){
if(n-i<j) continue;
for(int k=0;k<=n;k++){
if(k<=j&&f[now][j][k]){
//f->f
int fval=1ll*f[now][j][k]*w[i]%mod;
if(j){
upd(f[nxt][j-1][0],f[now][j][k]);
upd(f[nxt][j-1][k],mod-f[now][j][k]);
upd(f[nxt][j-1][k],fval);
upd(f[nxt][j-1][j],mod-fval);
}
//f->g
upd(g[nxt][j][1],fval);
upd(g[nxt][j][i-px+j+2],mod-fval);
}
if(1<=k&&k<=i-px+j&&g[now][j][k]){
//g->f
int gval=1ll*g[now][j][k]*w[i]%mod;
if(j){
upd(f[nxt][j-1][0],g[now][j][k]);
upd(f[nxt][j-1][j],mod-g[now][j][k]);
}
//g->g
upd(g[nxt][j][1],g[now][j][k]);
upd(g[nxt][j][k+1],mod-g[now][j][k]);
upd(g[nxt][j][k+1],gval);
upd(g[nxt][j][i-px+j+2],mod-gval);
}
}
}
for(int j=0;j<px;j++){
for(int k=1;k<=n;k++) upd(f[nxt][j][k],f[nxt][j][k-1]),upd(g[nxt][j][k],g[nxt][j][k-1]);
}
if(a[i+1]){
memset(f[nxt],0,sizeof(f[nxt]));// f' is invalid
for(int j=0;j<px;j++){
for(int rk=1;rk<=n;rk++){
int coef=C[a[i+1]-px-1][rk-1];
if(!coef||!g[nxt][j][rk]) continue;
//coef!=0 => j+rk\leq p_{i+1}\leq n
int t=j+a[i+1]-px-rk;
if(t<0) continue;
upd(f[nxt][t][t],1ll*g[nxt][j][rk]*coef%mod);
}
}
memset(g[nxt],0,sizeof(g[nxt]));
}
}
}
int ascend(int c,int _n,int _m,vector<int> p,vector<int> _w){
n=_n,mod=_m;
a[1]=1;
for(int i=1;i<=n;i++) a[i+1]=p[i-1]+(p[i-1]!=0);
a[n+2]=n+2;
for(int i=1;i<=n-1;i++) w[i+1]=_w[i-1];
w[1]=w[n+1]=1;
n+=2;
C[0][0]=1;
for(int i=1;i<=n;i++){
C[i][i]=C[i][0]=1;
for(int j=1;j<i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
DP();
return f[n&1][0][0];
}
```