LOJ3395 "2020-2021 集训队作业"Yet Another Permutation Problem
考虑什么样的排列可以通过 $k$ 次操作达到.不难发现当且仅当排列中存在一个区间,满足区间单增且区间长度 $\ge n - k$ .由于存在会比较难以统计,可以考虑求出所有极长连续段长度 $\le n - k - 1$ 的排列数量,然后用 $n!$ 减去即可.
考虑枚举 $t$ ,计算所有极长上升段都 $\le t$ 的方案数.考虑一个暴力,先暴力对整个序列分段,令这些段就是极长上升段,然后不难发现限制是 段内 $<$ 和 段间 $>$ .这个东西非常难以统计,所以考虑容斥掉 $>$ 符号,于是就会让一些