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

Lonely_NewYear · 2026-05-09 20:29:58 · 题解

一个自然的容斥做法。

不妨先枚举排列哪些位置是上升的，哪些位置是下降的，再计数这种情况的方案数。

如果既有上升也有下降的限制，限制情况比较复杂不太好做，考虑把其中一边容斥掉。

如果将所有上升容斥成下降，那么排列会被划分为若干个极长下降段。根据题目中的性质，所有未缺失位置上的元素是单调递增的，则每个下降段中至多有一个未缺失位置。

具体来说，对于一个位置：

则对于每个位置，强制其下降的系数为 1-w，不做任何限制的系数为 w。

继续考虑这个下降段的形式，若一个长度为 x 的下降段没有未缺失位置，则需要任意选择 x 个值填进去。否则其中只有一个未缺失位置，记这个位置的值为 p，同一下降段内左右分别有 x,y 个元素，则需要选择 x 个 >p 的值，y 个 <p 的值。

这与 P14364 [CSP-S 2025] 员工招聘的形式几乎一样。考虑从前往后 dp 这个结构的话，会依次有若干位置要求填入 >p 或 <p 的值，且 p 是递增的。考虑与这题一样的做法，把 >p 的限制全部容斥成 <p 的，在 dp 过程中记录有多少位置选择填入一个 <p 的值。

具体来说，记 f_{i,j} 表示将 1\sim i 分解为若干下降段，且选择了 j 个位置填入 <p。

记 b_i 为下标 \le i 的所有位置有多少空位，s_i 表示值 \le i 的有多少没有出现。

转移考虑往后枚举一个新的下降段 [i+1,k]：

若这一段没有未缺失值，则任意填入 k-i 个值，且降序排序。考虑 f_{i,j} 中已经包括了 b_i-j 个同类型转移，则需要把这 k-i 个数与 b_i-j 归并起来，系数为 b_i-j+k-i\choose k-i，转移到 f_{k,j}。这一部分复杂度 O(n^3)。
若这一段有一个未缺失值为 p，其左右各有 x,y 个位置，则需要填入 x 个 >p，y 个 <p 的数。枚举 x 中有 z 个容斥成 <p，剩余 x-z 个位置可以任意填入，则需要从 s_p-j 个 <p 的数中选择 z+y 个，再将 x-z 个和 b_i-j 归并，系数为 (-1)^z{s_p-j\choose z+y}{b_i-j+x-z\choose x-z}，转移到 f_{k,j+z+y}。这一部分复杂度 O(n^4)。
另外还有每个位置上升或下降的系数 w_i\prod_{l=i+1}^{k-1}(1-w_l)。

注意到事实上第二种转移分为 x,y 两步，可以分段转移。具体来说，若第 i 个位置未缺失，记 g_{i,j} 为 i 所在下降段左侧部分已经决策好，有 j 个 <p：

对于每个 f_{i,j}，记其右侧第一个未缺失位置为 k，其值为 p，则取下降段左侧部分 [i,k)，其长度为 x=k-i，枚举 z 个容斥掉，系数为 (-1)^z{s_p-j\choose z}{b_i-j+x-z\choose x-z}，转移到 g_{k,j+z}。
对于每个未缺失位置 i 和 g_{i,j}，枚举其右侧部分 (i,k]，其长度为 y=k-i，系数为 s_p-j\choose y，转移到 f_{k,j+y}。
另外还有每个位置上升或下降的系数。

容易分析其复杂度为 O(n^3)。