题意
给定 \(k\) 和一个排列 \(P'\)，问有多少个排列 \(P\) 以最少步数交换相邻两个元素来进行收敛，最终的排列可能是 \(P'\)，一个排列是收敛的当且仅当对于每一个数，在该数前且比这个数大的数的个数不超过 \(k\) 个。
思路
考虑正向的让一个排列收敛，我们设在第 \(i\) 个位置前且比 \(P_i\) 大的数有 \(cnt_i\) 个，最终收敛的条件为 \(\max\{cnt_1,cnt_2,\dots,cnt_n\} \le k\)。
考虑一次交换中 \(cnt\) 数组的变化，由于在 \([1,i-1]\) 区间的贡献对于 \(i\) 和 \(i+1\) 是可以直接交换的，我们只需要考虑 \(P_i\) 对 \(P_{i+1}\) 的贡献即可：
-
\(P_i > P_{i+1}\)，则交换后的 \(cnt_i\) 会少了原来 \(P_i\) 的贡献，故先交换，然后 \(cnt_i=cnt_i-1\)；
-
\(P_i < P_{i+1}\)，则交换后的 \(cnt_{i+1}\) 会多了原来 \(P_{i+1}\) 的贡献，故先交换，然后 \(cnt_{i+1}=cnt_{i+1}+1\)。
我们肯定不会对第二种情况进行交换，而对于第一种情况，我们也只会对原来 \(cnt_{i+1}>k\) 的位置进行交换，进一步考虑，发现第一种情况等价于 \(cnt_i < cnt_{i+1}\)，故交换的条件为：\(cnt_i < cnt_{i+1}\) 且 \(cnt_{i+1}>k\)。
接下来考虑从 \(P'\) 反着交换回 \(P\) 的情况，相当于前面的逆运算，我们设在第 \(i\) 个位置前且比 \(P_i\) 大的数有 \(cnt'_ i\) 个，则交换的条件为 \(cnt'_ i + 1 > cnt'_ {i+1}\) 且 \(cnt'_ i + 1 > k\)，又因为 \(P'\) 一定是已经收敛的数组，所以 \(cnt'_ i\) 一定不大于 \(k\)，故条件可进一步简化为 \(cnt'_ i = k\)。
每次交换相当于把这个数往后挪一位并加一，所以我们从后往前算方案数更方便。
对于最后一个满足 \(cnt'_ i = k\) 的 \(i\) ，它往后挪多少位都是可以的，而对于前面的，在它挪到上一个 \(cnt'_ i = k\) 现在所在的位置之前，显然也是可以的，而因为挪的过程中它会自增 \(1\)，所以前面来的数一定不会小于后面的数，所以在此时交换也是合法的。综上，对于每一个满足 \(cnt'_ i = k\) 的 \(i\)，都能随意往后挪动，至多可以挪动 \(n - i\) 次，故一共有 \(n - i + 1\) 中选择，所以答案为 \(\prod\limits_{cnt'_ i=k}(n-i+1)\)。
对于求 \(cnt'_ i\)，直接遍历是 \(O(n^2)\) 的，使用树状数组是 \(O(n\log n)\) 的，都可以通过本题（应该没人会在这里写分块啥的吧）。