Gym-101955C题解

题目传送门C - Insertion Sort

不重复题意了，直接写解的过程，场上推不出来，赛后看题解才推出来的

网上题解说存在 $k\ge n$k≥n的情况，然而我们特判 $k+1\ge n$k+1≥n的时候就直接输出 $n!$n!。

特判之后，必定是 $k\&lt;n-1$k<n−1。

现在来推一下,先不考虑前k项的 $k!$k!,后面再乘一下就算完了.

1.整一个序列完全有序的情况只有1种

2.当前k个数都是 $[1,k]$[1,k]的情况,在后面 $n-k$n−k个数里面选一个数,不放在自己的位置上,根据乘法原理,算出来就是 $(n-k)\ast (n-k-1)$(n−k)∗(n−k−1)

3.当前k个数不是 $[1,k]$[1,k]的情况下,而你又要保证最长上升子序列的长度是 $n-1$n−1,只能是一个完全有序的序列中,你在前k个数中拿一个数插入到 $[k+1,n]$[k+1,n]的其中一个位置中,有 $n-k$n−k种情况,根据乘法原理,算出来就是 $(n-k)\ast k$(n−k)∗k.

最后就是

$ans=\{\begin{array}{cc}n!,& k+1\ge n\\ k!\ast (1+(n-k)\ast (n-k-1)+(n-k)\ast k),& 1\le k\&lt;n-1\end{array}$ans={n!,k!∗(1+(n−k)∗(n−k−1)+(n−k)∗k),​ k+1≥n1≤k<n−1​