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

· · 题解

为了方便，将缺失值的位置的 p 设为 -1 而非题目中的 0，定义 p_0=0，p_{n+1}=n+1，w_0=w_{n}=1，这样第一个和最后一个位置的值都是确定值而非缺失值，而答案不变。

从后往前 dp，设计状态

f_{i,j} \quad (p_i \neq -1)

表示考虑填完了所有下标 \ge i 的位置的值，其中使用了 j 个 >p_i 的自由值（没有被确定位置的值）的所有方案的权值之和，容易算出使用了 j' 个 <p_i 的自由值。

当 i 转移时，它转移到下一个下标比它小的，且是确定值的位置 x，转移有两个难点：

先解决第一个难点，我们通过巧妙地设计状态来避免这个问题。

我们在上面设计的状态 f，其储存的是所有方案的权值之和。而「方案」这个说法其实是并不太严谨的，因为我们有两种理解方法：

  1. 记录具体是哪一个：总共 n 个数，已经选择了 i 个数，每次从中选择 j 个数就是 \binom{n-i}{j} 的方案。
  2. 记录相对大小关系：总共 n 个数，已经选择了 i 个数，每次从中选择 j 个数，相当于在 i 个数中插入 j 个数，就是 \binom{i+j}{j} 的方案。

对于所有 >p_i 的自由值的使用情况，我们记录其「具体是哪一个」，而 <p_i 的自由值的使用情况，我们记录其「相对大小关系」。

每次转移时，枚举 i,j（知道 i 后就可以求出 x，知道 j 后可以求出 j'），我们再枚举 k 表示之前填的 <p_i 的自由值中，前 k 大是在 (p_x,p_i) 之间的。

那么，我们可以求出值在 (p_x,p_i) 之间的自由值数量 t，则 dp_{j+k}\gets f_{i,j} \cdot \binom{t}{k}（这里不是直接赋值给 f_{x,j+k} 是因为还没有加上 x+1\sim i-1 的数，dp_j 记录的是考虑了下标 \ge i 的数，有 j 个 \ge p_x 自由值的数量）。

此时第一个难点已经解决了，由于中间枚举了 k，看起来是 O(n^3) 的，实际上 \sum k=O(n)，所以这里是 O(n^2) 的。

第二个难点相对好解决，设计状态 h_{l,a,b,c} 表示考虑到 l 这个位置，可用的比 l-1 的值大的自由值有 a 个，可用的比 l-1 值小的自由值有 b 个，可用的小于 p_i 的自由值有 c 个，的所有方案的权值之和。

那么我们枚举两个确定值 x,i 之间填了 a 个 >p_i 的自由值，b 个 (p_x,p_i) 的自由值，可以算出填了 c 个 <p_x 的自由值。

显然贡献就是 h_{x+1,a+b,c,b+c}。

外层枚举 i,j,k 是 O(n^2) 的，这里枚举 a,b 算贡献，总的复杂度是 O(n^4) 的。

而计算 h 数组也相对容易，首先 l 那一位可以用 a,b,c 算出，省去。我们每次枚举这一位选择比上一位小的还是比上一位大的，相应更新 a,b,c 即可，如果比上一位大，还可能产生 w 的贡献。直接实现是 O(n^4) 的，前缀和优化可以做到 O(n^3)。

综上，复杂度 O(n^4)，但是最内层循环只需要做加法和乘法，访问也很连续，常数也很小，所以跑的很快。