CCPC Recontest H Subpermutation


第一种是一个排列内部的可以直接统计
(ans=m!*(n-m+1)*(n-m)!)
第二种是两个排列的连接部分
对于一个排列(p),考虑在字典序下它的下一个排列q是什么样子的:
其实是p的最长下降后缀的前一位与最长下降后缀里比它大的最小的数交换位置,之后这个后缀从下到大排列
(p)合法一定是小于等于m的部分在首尾,大于m的在中间(设三段为(A,B,C)
方案数为(m!*(n-m)!*(m-1))
其中需要减去(q)不合法即首部在通过转化后变动的情况
这种情况一定最长下降后缀是(B+C),如果有(A)那一定不满足小于(x)的在首部了
所以不合法的方案数为

原文地址:https://www.cnblogs.com/AthosD/p/15390270.html