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

· · 题解

第一步容斥是不难的，令 w_i:=w_i-1，由组合意义知我们只需钦定上升而不考虑下降。

考虑最后的形态，每个位置的额外限制为在某个给出的值前/后，或者之间的特殊情况。

在模合数意义下再进一步容斥是困难的，我们考虑钦定计数。我们只需为每个 p'_i=j 钦定一个好的贡献时刻，我们相当于同时扫描序列和值域，在 (l,r) 中，我们在 l 后连的上升段时加入数 (p_l,p_r) 的数，对于尚未决策的数决定其顺序，理解了这些转移系数是不难根据意义写出的。

如果理解不深刻，我们可能需要单独处理不连接任何点的上升段。O(n^3) 则需要一些手法：根据 DP 的含义，我们区分了两个值域，我们考虑将上升段分为这两个类型的段，在切换类型和开新的段时贡献系数。

我们记 f_{i,j,l,0/1} 表示转移到 i，有 j 个已经确定，当前段长 l，类型为前/后，转移是分步的，因此转移是 O(1) 的，系数严格根据意义，特殊处理给出的位置即可。