P16433 题解

· · 题解

给一个两次容斥做法。

考虑 p_i=0 怎么做，发现可以直接对上升段容斥，即把序列划分为若干段并强制让段内上升，中间的连接位置不管，然后钦定 k 个连接点也是上升的并带上 (-1)^k 的系数。发现这个不是很好推广，但是注意到已经确定的位置是上升的，于是改为钦定下降段。这样每一段内显然只会包含至多 1 个已经确定的位置，形式相对简单。这样如果钦定 [l,r] 下降，其内部的位置可以选择不分段，也可以分段后钦定合并并带上 -1 的系数，总转移系数就是

\begin{aligned}\prod\limits_{i=l}^{r-1}(1-w_i)\end{aligned}

考虑如果钦定区间 [l,r] 为下降段且包含已经确定的位置 p_i 的话该如何转移。发现这等价于从所有数中选一些数到这个区间里，且恰好有 i-l 个数大于 p_i。直接做的话有两个方向的限制并不好做，考虑再容斥一步，强制有 k\ge i-l 个位置大于 p_i，根据二项式反演的结论容斥系数是 (-1)^{k-(i-l)}\times \dbinom{k}{i-l}。

于是到这里做法就比较显然了，从大往小 DP，记录 f_{i,j} 表示考虑到 i，当前选择了 j 个更大的数（即上一步 k 的总和是 j）。转移需要枚举选择的区间 [l,i-1]，如果包含关键点的话还需要枚举 k，系数可以直接组合数算出来，总复杂度 O(n^4)。

上面那个做法的瓶颈是枚举 k，但是对于一段 [l,r] 的转移，显然满足 >p_i 的值是一段前缀，因此可以直接分步转移，记录一个 0/1 表示当前是否选完了一个完整段即可。复杂度 O(n^3)。

我没拿到代码。