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

Neuro_MLE · 2026-05-09 19:28:14 · 题解

前言

哎哎哎，送上 Ag 的题。别问我为什么不会 T2，问就是因为纯菜。

事后更新：有 T1 的加持，还是拿不下 Ag 吗。

感谢 Register_int 大哥在 APIO 前几天在 LA 里带我补习组合计数 /bx

思路

将所有 w 减去 1，转为钦定形式（也就是说把 \prod_{i\in S}w_i 的形式转化成 \sum_{T\sube S}\prod_{i\in T}(w_i-1)，其中 T 就是钦定一定上升的位置）。后文默认 w 都被减过了。

由于题目不保证模数 m 的范围，所以需要竭力避开除法操作，不能涉及到乘逆阶乘操作。

对于一个位置 i，设它及之前第一个非 0 位置是 c，值是 v（不存在就均为 0），f_{i,j} 为前 i 个元素，有 j 个 \le v 的元素且钦定了这 j 个元素和其余 i-j 个元素的大小关系时的权值和。

• 如果 p_i=0，那么枚举 i 被涉及到的极长连续上升段 [i',i]，其中 c\le i'\le i（强行在 c 左侧打隔断），其中有一位置 k 使得 i'-1\le k\le i，在 k 及之前的元素 <v 而在 k 之后的元素 >v。这样会使 j 增加 k-i'+1，方案数为 f_{i'-1,j} 乘剩余 v-j 个值有顺序地选 k-i'+1 个值以及把往 i'-1-j 个 >v 的值里插入 i-k 个已知大小顺序的值的方案数，再乘 \prod_{i'\le c<i}w_c。直接枚举会爆，所以我们对这个断点 k 再开一个 dp 数组处理。

• 如果 p_i\not=0，那么设上一个非 0 在位置 c'，值是 v'。枚举 i 被涉及到的极长连续上升段 [i',i]，其中 c’\le i'\le i。

  • 如果 i'>c'，由于我们拓展了 v，所以考虑 f_{i'-1,j} 的贡献：对于未选中的 i'-1-j 个 >v' 的元素，枚举数量 m，从 (v',v) 中有顺序地选择 m 个值分配给钦定的顺序中的前 m 小，使得 j 增加 m。对于新的 j，我们从 v-1-j 个值中选择 i-i'-1 个，然后将 j 增加 i-i'-1。
  • 如果 i'=c'，由于左端点右端点都是固定的，那么考虑 f_{c',j} 的贡献：先从 (v',v) 中有顺序地选择 i-c'-1 个元素分配给两个位置中间的所有位置，然后枚举 m，从新增的 (v',v) 除去 i-c'-1 个值中有顺序地选择 m 个值分配给钦定顺序中的前 m 小，将 j 增加 i-c'-1+m。
  • 上文略去了 w 的贡献。最后更新 c,v。由于每个 i' 在这一步都只贡献了至多两次 O(n^2) 的转移，所以复杂度是对的。

然后我们就成功绕开除法操作在 O(n^3) 时间复杂度内解决了这道题。

如果上面有疑似出错的地方或者看不懂的地方，可以看代码配合理解。

代码

代码等 CCF 发。不发我就再写一份。

代码重写了，使用了好朋友 AVENGER_M 的码风 /mgx

#include<bits/stdc++.h>
#define lglg long long
using namespace std;

int cid,n;
lglg modp,wei[505],iwei[505][505],C[505][505],f[505][505],g[505][505];

int ascend(int CI,int N,int M,vector<int>P,vector<int>W){
    cid=CI;n=N;modp=M;for(int i=1;i<n;i++)wei[i]=(W[i-1]+modp-1)%modp;
    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])%modp;
    }
    for(int i=1;i<=n;i++){
        iwei[i][i-1]=1;for(int j=i;j<n;j++)iwei[i][j]=iwei[i][j-1]*wei[j]%modp;
    }
    f[0][0]=1;int val=0,lst=0;
    for(int i=1;i<=n;i++){
        if(P[i-1]==0){
            for(int j=lst;j<i;j++)for(int k=0;k<=val;k++){
                f[i][k]=(f[i][k]+f[j][k]*iwei[j+1][i-1]%modp*C[i-k][i-j])%modp;
                if(k+i-j<=val)g[i][k+i-j]=(g[i][k+i-j]+f[j][k]*iwei[j+1][i-1]%modp*C[val-k][i-j])%modp;
            }
            for(int j=lst;j<=i;j++)for(int k=0;k<=val;k++){
                f[i][k]=(f[i][k]+g[j][k]*iwei[j][i-1]%modp*C[i-k][i-j])%modp;
            }
        }
        else{
            int v=P[i-1];
            for(int j=lst;j<i;j++)for(int k=0;k<=val;k++)for(int kk=k;kk<v;kk++){
                if(kk+i-j<=v)f[i][kk+i-j]=(f[i][kk+i-j]+f[j][k]*iwei[j+1][i-1]%modp*C[v-val-1][kk-k]%modp*C[v-kk-1][i-j-1])%modp;
            }
            if(lst&&v-val>=i-lst)for(int k=0;k<=val;k++)for(int kk=k;kk<v;kk++){
                if(kk+i-lst<=v)f[i][kk+i-lst]=(f[i][kk+i-lst]+f[lst][k]*iwei[lst][i-1]%modp*C[v-val-i+lst][kk-k]%modp*C[v-val-1][i-lst-1])%modp;
            }
            for(int j=0;j<=v;j++)g[i][j]=f[i][j];
            lst=i;val=v;
        }
    }
    int ans=f[n][val];memset(C,0,sizeof(C));memset(f,0,sizeof(f));memset(g,0,sizeof(g));
    return ans;
}