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

ty_mxzhn · 2026-05-12 00:36:18 · 题解

零次容斥你赢了。一次容斥做法报道。

第一次容斥很显然：原题的式子为：\displaystyle \prod_{i=1}^{n-1}[p_i<p_{i+1}]w_i+[p_i>p_{i+1}]，调整一下得到 \displaystyle \prod_{i=1}^{n-1}[p_i<p_{i+1}](w_i-1)+1，分配律一下，发现是钦定一个上升集合。如果钦定了上升集合，序列就会分成若干段，每一段内是一个连续上升子序列，然后我们又有一个上升子序列被限制了。

设计一下 dp：f_{i,j} 表示前 i 个数有 j 个比前 i 个数“限制的最大值”大。这 j 个数的相对位大小关系已确定，并且“限制的最大值”往下的待填值域位置已经确定了部分。

接下来开始赤石！

首先，图一表示了一段内可填数的结构，可以分段转移：保证每一段的两端至少有一个是限制点，并且中间没有限制点。需要注意的是，切出来的段可能有长度至多为一的交。

图二是 Case 1：右端是限制点，最值变大，需要在枚举 i,j,k 后枚举上一个限制有多少个仍在新的限制内，记为 c，然后对于新的一段，计算剩余的位置个数：

• 中间空余位置 nw-ls-1 个。
• 不在新的限制内的数 k-c 个。
• 下方空余位置 j-k-1 个。
• 转移到 f_{i,c}，从 f_{j,k} 来。
• 系数包含选择丢失限制的数的位置，给新一段内的数排位置，和这个段本有的系数。

图三是 Case 2：红线画错了，应该往上到第二个位置。总之和上一个 Case 大致相同。

图四是 Case 3：限制不变，直接加入即可。

图五是 Case 4：无限制，需要枚举放在上方几个，又因为 (i,j) 数量是 n^2 级的，所以是 O(n^4)，获得 65 分，气笑了。这个不能用前缀和优化，那咋办。

优化

如果直接从式子的角度优化是不好做的。

图六把 Case 3 和 Case 4 合并：因为 Case 3 是 O(n^2)，Case 4 是 O(n^4)，感觉还能蒸。

现在一次转移一个 A 段和若干个 B 段。

从 Case 1 获得启示：可以有一个 O(n^4) 做法，用范德蒙德卷积优化到 O(n^3)。

图七：目前红线上方有 k 个点，下方有 p-k-1 个点，p 是限制点的位置，最后总共增加 i-p 个紫点，枚举最后增加在上方的点数 c，此时枚举量为 n^3，目标变成钦定了 (i,p,k,c) 后求方案数。然而 k 在后续无贡献（但有系数），可以扔掉 k，只需固定 (i,p,c)。

A 段把上方若干个点变成棕点，对于 (i,p,c) 再枚举 A 段结尾的位置 j，枚举量为 (i,j,p,c)，仍然是 O(n^3)，目标变成钦定了 (j,i,c) 后求方案数，然而 c 和后续无关，可以扔掉 c，只需固定 (j,i)。