题解：P17801 [CXOI2026] 大潘小潘向前 p

· · 题解

+ $a_i$ 在给定范围 $[1,b_i]$ 内。 + 恰好存在 $k-1$ 个位置 $i$ 满足 $1 \le i < n$ 且 $a_i > a_{i+1}$。 $2$ 限制等价于恰有 $n-k$ 给不降位置。 冥冥之中联想起 ARC115E（虽然并无关联），考虑容斥。设 $f_{i,j}$ 表示 $1 \sim i$，钦定至少有 $j$ 个不降位置时的方案数。则最终对于 $k$ 的答案即为 $\sum\limits_{i \ge n - k} (-1)^{i-(n-k)}\binom{i}{n-k}f_{n,i}$。 $a_i > a_{i+1}$ 的位置把 $a$ 划分为若干不降子段，转移考虑枚举上一个段的结尾 $k$，则 $f_{i,j} \gets f_{i,j}+f_{k,j-(i-k-1)}g_{k+1,i}$。其中 $g_{l,r}$ 表示 $a_{l \sim r}$ 构成不降序列的方案数。 难点变为求 $g_{l,r}$。考虑 $r$ 固定时，$l$ 从 $r$ 到 $1$ 求解，不妨认为 $g_{r+1,r}=1$，令 $c_i=\min\limits_{j=i}^{r} b_j$。 新加入 $a_l$ 时，一个显然的事是必然 $1 \le a_l \le c_l$ 才有方案能构成非降序列。继续容斥。 + 不管 $a_l,a_{l+1}$ 关系，而后 $a_{l+1 \sim r}$ 不降。方案数 $\binom{c_l}{1}g_{l+1,r}$。 + 但是上个情况不能保证 $a_{l} \le a_{l+1}$，也就是说你把 $a_l > a_{l+1}$ 的方案也算了。减掉 $\binom{c_l}{2}g_{l+2,r}$。 + 但是上个情况不能保证 $a_{l+1} \le a_{l+2}$，也就是说你把 $a_l > a_{l+1} > a_{l+2}$ 的情况多减了，实际只要减 $a_l > a_{l+1} \le a_{l+2}$ 的情况，所以还要加回 $\binom{c_l}{3}g_{l+3,r}$。 + 以此类推。 所以根据容斥，有递推式 $g_{l,r}=\sum\limits_{k=1}^{r-l+1} (-1)^{k-1}\binom{c_l}{k}g_{l+k,r}$。可以 $O(n^3)$ 直接算。最后暴力 DP 求出 $f$ 再容斥回去即可。