题解：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}$，暴力求逆元，用快速幂计算式子后半部分即可。