2021CCPC网络预选赛（重赛） 【待补完】

比赛链接
过了6题。遗憾的是1008我推的式子漏了一种情况，最后一小时都没看出来。太可惜了。

1008

分析：

分成两部分来算。第一部分是在每个n排列内部的m排列，可以直接算：

$ (n-m+1) * m! * (n-m)! $

第二部分是在两个n排列之间的m排列。
首先，设两个相邻的n排列是p1和p2，那么p2就是：找到p1的最长下降后缀s，将s的前一个数字x与s中大于x的最小数字y交换，再把y后面的部分从小到大排序。
想清楚这点就好说了。当时我这里想错了，以为x是与s中的最小数字交换囧。
然后可以确定的是，如果p1和p2之间有m排列，那么p1的形态一定是：
一段 $ [1,m] $ 的数（记作A） + 一段 $ [m+1,n] $ 的数（记作B） + 一段 $ [1,m] $ 的数（记作C）。
证明这一点需要用到p1到p2的变化规律：
如果p1是上述形态，易知p2的形态是 $ A + ... $ ，那么p1的C和p2的A组成一个m排列。
如果p1不是上述形态，要想满足条件，p1总要存在一个后缀C满足：C中的数都 $ \in [1,m] $ 。那么它需要p2的形态是 $ A + ... $，其中A由 $ [1,m] $ 去掉C中的数后剩下的数组成。根据变化规律可知p1一定有前缀A。这是由于p1的最长下降后缀的开头不会是首部（称第一个大于m的数字之前为首部）的后一个数字（因为首部后面、C前面还有 $ \in [1,m] $ 的数），则p1到p2首部不会改变。所以p1的首部是A，与假设矛盾。
然后我们考虑变化发生在C内的情况：只要C不是递减的，那么p1到p2的变化发生在C内，那么可以得到m排列。这部分的答案是：

$ \sum_{i=1}^{m-1} C_{m}^{i} * (i!-1) * (m-i)! * (n-m)! $

然后当时我以为C递减的情况就不能得到m排列了，导致WA了半天最终没过……
实际上C是递减的情况也可以得到答案。只要不是从A往后都递减，那么p2的首部就还是A。所以这部分的答案是：

$ \sum_{i=1}^{m-1} C_{m}^{i} * (m-i)! * ( (n-m)! - 1 ) $

全部加起来，总答案是：

$ m! * (n-m)! * n - m! * \sum_{i=1}^{m-1} \frac{1}{i!} $

预处理就可以 $ O(1) $ 得到每次的答案了。