给一个序列，如果经过k次冒泡能使其变为单增序列，则称该序列为k回合冒泡序列
现在给你n,k， 问在n的全排列中，k回合冒泡序列有多少个
这题看规模就是要推一个公式出来
discuss里的一个解法非常好，让人可以理解
对于n个元素，假设为{0,1,...n- 1},可以发现
对于任意一个排列，假设L(i) 表示位置i上的元素的前面有多少数字比它大, 那么得到了一个L序列。
那么可以知道 交换的轮数 = max{ L(i) } (0 <= i < n)并且可以发现，对于所有n!种序列,其L序列满足:{[0,0],[0,1],[0,2]...[0,n-1] }...(1)[a,b] 表示值在[a,b] 之间，包含对于满足(1)的任意一个L序列，必然可以构造出一个对应的序列。于是可以知道题目所求的就是max{L[i]} = k的种类数
于是我们考虑
1 * 2 * 3 .. * k * (k + 1) ^ (n - k),就是后面的从第k项开始，全部取[0,k],前面任意取
之后扣除 1 * 2 * 3 * ... * k * k^(n - k + 1) ,就是后面第k项开始 [0,k - 1]，前面任意取于是ans = k! * ((k + 1) ^ (n - k) - k^(n - k))对于k!,o(1000000)预处理即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <map>
#include <ctime>
#define MAXN 222
#define MAXM 6122222
#define INF 1000000001
using namespace std;
int fac[1111111];
int mod = 20100713;
long long fastmod(long long a, long long b, long long c){long long ret = 1;a %= c;for(; b; b >>= 1, a = (a * a) % c)if(b & 1)ret = ret * a % c;return ret;
}
int main() {fac[0] = 1;for(int i = 1; i <= 1000000; i++) {long long tmp = (long long)fac[i - 1] * (long long)i % mod;fac[i] = tmp;}int T, n, k;scanf("%d", &T);while(T--) {scanf("%d%d", &n, &k);long long tmp = (long long)fac[k] * (fastmod(k + 1, n - k, mod) - fastmod(k, n - k, mod) + (long long)mod) % mod;printf("%I64d\n", tmp);}return 0;
}