题解：P10004 [集训队互测 2023] Permutation Counting 2

· · 题解

听说省选前写题解可以攒 rp？

这道题是集训的时候 wishapig 大神讲的，膜拜。

题意即为有多少个原排列恰好有 x 个上升、逆排列恰好有 y 个下降，我们发现“恰好”这个不太好表述，我们可以考虑计算原排列至少有 x 个上升、逆排列至少有 y 个下降的方案数。具体的，设 f_{i,j} 表示原、逆排列恰好有 i 个上升、j 个下降，g_{i,j} 表示原、逆排列至少有 i 个上升、j 个下降，我们可以二项式反演：

g_{i,j}=\sum_{x \ge i,y \ge j}\binom xi \binom yj f_{x,y} \iff f_{i,j}=\sum_{x \ge i,y \ge j}(-1)^{x-i} \binom xi (-1)^{y-j} \binom yj g_{x,y}

显然可以通过将 x 和 y 两维分开来，预处理 \sum_{y \ge j} (-1)^{y-j} \binom yj g_{i,y}，即可 \mathcal{O}(n^3) 完成 g 到 f 的运算。于是我们现在的问题来到如何计算 g？

接下来就是最近巧妙的一步：钦定原、逆排列分别有 i,j 个下降，即有 i,j 个上升段，我们考虑逆排列到原排列的过程，即值与下标互换，我么通过这样的方式将逆排列的数填入原排列中即可得到（至多）i 个上升段。这个过程即为：决策逆排列的第 x 个上升段中有多少个被填入了原排列的第 y 个上升段，设其为 c_{x,y} 表示为矩阵，我们可以发现满足要求的排列的矩阵 c 满足任意一行一列的和均大于 0（不妨模拟这个过程思考一下），由此我们将 g 的计算转化为有多少个固定大小的矩阵满足行列和均为正且和为 n。

这个仍然是比较难做的，于是我们考虑不限制行列和为正的再进行二项式反演，不限制行列和、大小为 m 的矩阵显然有 \binom {n+m-1}{m-1}，二项式反演的过程也可以用类似上面的方法优化至 \mathcal{O}(n^3)。于是总时间复杂度 \mathcal{O}(n^3) 很精妙地完成了这题。听说可以通过任意模数 NTT 做到 \mathcal{O}(n^2 \log n)，但是我不会。

代码实现可以参考其他题解。