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

chenwenmo · 2026-05-12 09:47:59 · 题解

容斥做法

先考虑全 0 怎么做。

有个基本的思路是，先确定 f(q) 的值，然后计算有多少种方案满足这个值。

不难想到可以对上升子段做 DP，设 f_i 表示前 i 个位置的所有方案权值和，那么 f_i = \sum\limits_{j=1}^{i} f_{j-1} \cdot \binom{n-j+1}{i-j+1} \cdot \prod\limits_{k=j}^{i-1} w_k，

但这样显然会算多，比如对于一个划分方案 ../...，贡献为 w_1w_3w_4，但还会计入一些不合法的排列，如 [1,2,3,4,5]，实际贡献应该是 w_1w_2w_3w_4。

也就是对于一个划分方案，我们希望只计算断点处是下降的排列数。按照上述 DP 方式计算的方案不会考虑这一限制。

不妨考虑容斥，设一个划分方案的断点集合为 S，枚举 T\subseteq S，钦定 T 中的断点不合法（即上升），容斥系数为 (-1)^{|T|}。

这样也不太好直接 DP，我们可以把原方案的 T 中的断点处合并，得到一个新的方案，新方案断点集合为 S\setminus T，在新方案处算贡献即可，

然后考虑怎么推广到一般情况。

对于原本就给定的上升位置，贡献是固定的，最后再乘即可。

我们只需考虑 p_i=0 的连续段，以及，该连续段两端的非零位置。

如果划分的子段 p_i=0，这一部分是好算，重点考虑同时包含 p_i\ne 0 的子段。

发现这时候不能随便选排列了，必须满足形如 <p_i 或 >p_i 的限制，由于题目保证非零位置递增，且我们是顺序 DP，因此希望只保留 <p_i 的限制。

对于 >p_i 的限制，考虑容斥，枚举钦定 t 个数 <p_i，剩下的数随便选，容斥系数为 (-1)^{t}，

设 f_{i,j} 表示前 i 个位置，已经填了 j 个带限制的数，考虑转移：

• 设 e_i=\sum\limits_{j=1}^{i}[p_j=0]，v_i=\sum\limits_{j=1}^{i}[\nexists p_k=j]，
• 若 p_i\ne 0 且 p_{i-1}\ne 0，f_{i,j}=f_{i-1,j}。
• 否则往前枚举一个子段 [k,i]，设 a=\prod\limits_{t=k}^{i-1}(w_t-1)，
  • 若 p_i=p_k=0，f_{i,j} \gets f_{k-1,j} \cdot \binom{e_i-j}{i-j+1} \cdot a。
  • 若 p_i=0,p_k\ne 0，枚举 t 表示钦定几个数 <p_k，记 len=i-j,lst=j-t，f_{i,j}\gets f_{k,lst}\cdot (-1)^{t} \cdot \binom{v_{p_k}-lst}{t} \cdot \binom{e_i-j}{len-t} \cdot a。
  • 若 p_i\ne 0,p_k\ne 0，也是枚举 t，记 len=i-k-1,lst=j-len，f_{i,j}\gets f_{k,lst}\cdot (-1)^{t} \cdot \binom{v_{p_k}-lst}{t} \cdot \binom{v_{p_i}-lst-t}{num-t} \cdot a。
  • 若 p_i\ne 0,p_k=0，记 len=i-k,lst=j-len，f_{i,j}\gets f_{k-1,lst}\cdot\binom{v_{p_i}-lst}{len}\cdot a。

看起来是 O(n^4) 的，但不难发现需要枚举 t 的区间 [k,i] 只有 O(n) 个，因此复杂度是 O(n^3) 的。

Code