POJ 3761 Bubble Sort 冒泡排序的扩展

给一个序列，如果经过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;
}