题目
题目描述
在 MT 刚接触到了冒泡排序的时候，觉得这个东西太慢了，但是加上 break 的效果怎么样呢？于是他开始考虑这样一个问题：任意一个 $N$ 的排列中，有多少种需要恰好扫 $K$ 次才能使得数列从小到大排列。所谓扫就是第一重循环，当数列有序后程序会自动退出循环。
冒泡排序的代码：
1
2
3
4
5
6
7
for(int i=1;i<=n;i++){
for(int j=n;j>i;j--){
if(a[j]<a[j-1]){
swap(a[j],a[j-1]);
}
}
}
输入格式
第一行一个数 $T$，表示数据组数。
接下来 $T$ 行，每行两个整数 $N,K$。
输出格式
$T$ 个数，表示答案模 $1000000007$ 的结果。
输入输出样例
输入
1
2
3
4
3
3 0
3 1
3 2
输出
1
2
3
1
3
2
说明/提示
样例解释
枚举六种情况即得。
数据范围
对于前 $30\%$ 的数据，$T\leq 10,N\leq7$。
对于 $100\%$ 的数据，$1\leq T\leq100000,1\leq N\leq1000000,0\leq K\leq N-1$。
题解
显然是个组合数学题。
先说结论，对于一组给定的 $n,k$，答案为： \(k!\left[(k+1)^{n-k}-k^{n-k}\right]\) 考虑如何证明。
首先，冒泡排序是从前往后还是从后往前是不影响结果的，因此考虑从前往后移的写法。
令 $d(x)$ 表示排列中，第 $x$ 个数前面的大于 $x$ 的数的个数。
例如对于排列 $\langle3,2,4,1,5\rangle$，有 $d(1)=0,d(2)=0,d(3)=2,d(4)=0,d(5)=4$。
令 $f(x)$ 表示排列中，$x$ 是第几个数。
例如对于排列 $\langle3,2,4,1,5\rangle$，有 $d(1)=4,d(2)=2,d(3)=1,d(4)=3,d(5)=5$。
那么对于题目中的“扫描 $k$ 次”，即：
\[\max_{i=1}^n d(i)=k\]因为每扫一遍，对于任意一个 $d(x)$ 都只会至多减少 $1$。那么，我们就将原来的问题转化为了 $d(x)$ 满足条件的数列问题。
显然，在一个排列中，对于最小数 $m$ 有：$d(f(m))=f(m)-1$。（$m$ 不一定为 $1$）。
考虑在 $1\sim n$ 的排列中，$d(f(1))\leq k$，有 $f(1)\leq k+1$，$f(1)$ 有 $k+1$ 种可能，$1$ 有 $k+1$ 种放置方案。
对于 $2$，可以考虑 $2\sim n$ 的新排列，暂时不放置 $1$。则 $d(f(2))\leq k$，有 $f(2)\leq k+1$，$2$ 有 $k+1$ 种放置方案。此时再将 $1$ 插入，不影响最终答案。
对于 $3,4,5,\cdots,n-k$，有前 $n-k$ 个数的放置方案数为：
\[(k+1)^{n-k}\]对于后 $k$ 个数，不可能出现某一个数 $x$ 满足 $d(x)>k$，因此排列方案数为 $k!$。
故，$\max\limits_{i=1}^nd(i)\leq k$ 的方案数为：
\[k!(k+1)^{n-k}\]同理，所有 $\max\limits_{i=1}^nd(i)\leq k-1$ 的方案数为：
\[(k-1)!k^{n-k+1}\]总方案数即：
\[k!(k+1)^{n-k}-(k-1)!k^{n-k+1}=k!\left[(k+1)^{n-k}-k^{n-k}\right]\]AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1000000,P=1000000007;
int a[N+1]={1};
void pre(){
for(int i=1;i<=N;i++){
a[i]=1ll*a[i-1]*i%P;
}
}
int qpow(int a,int n){
if(!n){
return 1;
}
int t=qpow(a,n>>1);
t=1ll*t*t%P;
if(n&1){
t=1ll*t*a%P;
}
return t;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
pre();
int T;
scanf("%d",&T);
while(T--){
int n,k;
scanf("%d %d",&n,&k);
printf("%d\n",1ll*a[k]*(qpow(k+1,n-k)-qpow(k,n-k)+P)%P);
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
