题目链接：https://vjudge.net/problem/POJ-3761
题意：给出n和k，求通过k趟冒泡排序得到长为n的有序排列（元素为n个不同的数）的原排列有多少个。
思路：
先给出反序表的定义：
令bi(1<=i<=n)為位於i左邊但是大於i的元素個數，就能得到排列a1,a2,...,an的反序表b1,b2,...,b3。比如說，排列5 9 1 8 2 6 4 7 3有反序表2 3 6 4 0 2 2 1 0（在1左邊且大於1的有2個，在2左邊且大於2的有3個，……）。
再给出反序表的重要结论：
第1個元素的反序數取值範圍是[0,n-1]，第i個元素的反序數取值範圍是[0,n-i]，最後一個元素的反序數只能是0。并且每個反序數可以在區間內任意取值而不用考慮其他反序數的值，也就是說反序數是相互獨立的。（因为第一个元素的反序数[0,n-1]分别对应n个位置中的一个位置，确定之后去掉这个位置，剩下n-1个位置; 第二个元素的反序数[0,n-1]对应这n-1个位置中的一个，确定之后去掉这个位置，剩下n-2个位置......这样可以得到所有反序表对应的原排列有n!个，原排列本身最多只有n!个，所以反序表和原排列是一一对应的，且反序表中反序数相互独立。）
回到题目：
不难发现每一趟冒泡排序都会将剩下的>0的反序数减一，所以题目就转变乘最大反序数为k的反序表个数。所以我们可以通过求最大反序数<=k的反序表的个数，元素i的反序数为n-i，令n-i<=k得i>=n-k，即>=n-k的元素其反序数恒<=k，所以其反序数的值可以是其范围内的任意值，共有(k+1)!种可能。对于i<n-k，其反序数范围为[0,k]，即k+1种，则共有(k+1)^(n-k-1)种可能。两者相乘得k!*(k+1)^(n-k)。
同理求出最大反序数<=k-1的个数，相减得k!*[(k+1)^(n-k)-k^(n-k)]。
然后打表阶乘，利用快速幂取模即可。
AC代码：
#includeusing namespace std;typedef long long LL;const int maxn=1000005;const int Mod=20100713;int T;LL f1[maxn];void init(){ f1[0]=f1[1]=1; for(int i=2;i<=1000000;++i) f1[i]=f1[i-1]*i%Mod;}LL qpow(LL a,LL b){ LL ans=1; while(b){ if(b&1) ans=(ans*a)%Mod; a=(a*a)%Mod; b>>=1; } return ans;}int main(){ init(); scanf("%d",&T); while(T--){ LL n,k; scanf("%lld%lld",&n,&k); printf("%lld\n",f1[k]*(qpow(k+1,n-k)-qpow(k,n-k)+1LL*Mod)%Mod); } return 0;}