题目链接：

转自：

题目大意

 　　含 n 个不同元素的排列恰好经过 k 趟冒泡排序变得有序。问原数组有多少种排列情况？

分析

　　第一眼看上去觉得是个 DP，最后发现是个数学题，认栽。。。

　　

　　首先，定义 f(x) 表示在数组中位于元素 x 左面且大于 x 的个数。那么有$0 \leq f(x) \leq n - x$。

　　定义 g(x) 为经过不超过 x 趟排序的排列数。于是答案就为 g(k) - g(k - 1)。

　　由题意得$k = f(x)_{max}$，因为冒泡每次直冒一个数，因此每轮只有一个数会冒到 x 后面，对其他数也是一样，也就是每一趟排序$对\forall_{1 \leq x \leq n, f(x) > 0} f(x) = f(x) - 1$。

　　接下来推 g(k)。

　　由于$k \geq n - x$，所以$x \geq n - k$。

　　所以当$x \geq n - k$时，放哪里都可以；而当$x < n - k$时，某些地方是不能放的。

　　先放后 k 个数，一种有 k! 种排列。

　　对于前 n - k 个数，从小到大排列，然后与后 k 个数的排列合并：$[1, 2, 3, \dots, n - k, a_1, a_2, \dots, a_k]$。

　　从 1 开始，1 可以不动，也可以与数组中比它大的前 k 个数中的某一个对调，有 k + 1 种。

　　2 在 1 的基础上同理，也有 k + 1 种。

　　于是前 n - k 个数总共有$(k + 1)^{n - k}$种。

　　那这样做会不会有重复呢？不可能，因为是从小到大遍历的，所以 x 一旦调出去，就不可能再被调回来。

　　因此$g(k) = (k + 1)^{n - k} * k!$。

　　所以$g(k) - g(k - 1) = k! * ((k + 1)^{n - k} - k^{n - k})$。

代码如下

1 #include 
       
          2 #include 
        
           3 #include 
         
            4 #include 
          
             5 #include 
           
              6 #include 
            
              7 #include 
             
               8 #include 
              
                9 #include 
               
                 10 #include