题解：P14352 排序

FstAutoMaton · 2025-10-31 15:13:31 · 题解

P14352 排序

赛前写题解加 rp。

题解全是看不懂的高级推法，给个排序网络的思路。

先把 n<k 的情况判掉，此时答案为 n!。

根据排序网络的经典结论，一个排列 p 合法当且仅当对于任意 i，将小于等于 i 的数视为 0，大于 i 的数视为 1，按位置排序第 k+1 个 1 所在位置之后的所有数都为 1。

对于一个确定的 i 进行考虑，设 1 的位置序列为 pos，那么上述事情等价于 pos_{k+1}\sim n 中的数全都大于 i，即 pos_{k+1},pos_{k+2}\cdots,pos_{n-i} 是连续的且 pos_{n-i}=n。那么就等价于原排列上后 n-i-k 个数全部都大于 i。

PS：关于为什么是后 n-i-k 个数，原因是在 pos 序列中 k+1\sim n-i 一共有 n-i-(k+1)+1=n-i-k 个 1，所以得到了上面的东西。

继续转化，可以转化为 \min_{j=i+k+1}^{n}a_j>i。注意到对于一个位置，最大的限制到其的 i 的限制是最严格的，所以只需要考虑 a_{i+k+1}>i 即可。

令 i\rightarrow i+1，则 a_{i+k}\geq i\ ,i\in\left[1,n-k\right]，那么考虑按照从小到大的顺序将 1,2,\cdots,n-k-1,n-k 填入序列，每次填一个数相较于上一个数会多一个合法位置，但上一个数填完后消耗了一个位置，所以 1\sim n-k 全部都有 k+1 个位置可以填，而 n-k+1\sim n-k 这些数全部都不需要考虑位置，直接选没填的位置填即可。所以最终的答案为 k!\times (k+1)^{n-k}，暴力求逆元，用快速幂计算式子后半部分即可。