自动搬运

查看原文

来自洛谷，原作者为

	saltFish 额

搬运于2025-08-24 22:29:25，当前版本为作者最后更新于2022-06-14 13:38:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意很明显，该伪代码就是归并排序的版子，只不过是规定了层数为 $(k-1)$。

我们知道对于一个有 $x$ 个数的子序列它本身有序的概率是 $\dfrac{1}{x!}$。

因为归并排序是从中间划分并递归，所以在第 $k-1$ 层的划分序列必定是 $\dfrac{n}{{2}^k}$ 或 $\dfrac{n}{{2}^k}+1$ 向下取整。而这两种子集的数量是可以求出来的的，留给读者思考，在代码中也有体现。

只要将全排列数 $n!$ 乘上每一个第 $(k-1)$ 层子集有序的概率就能得出最终的答案。

而对于分数的乘法相当于除法，在需要取摸的情况下要求逆元。

特殊的，对于 $n \le {2}^k$ 的情况，无论序列如何都可以完成排序，所以答案为全排列数 $n!$。

但由于 $k$ 可能会很大，而当 $k > 20$ 时 ${2}^k$ 一定大于任意的 $n \le {10}^6$。为了避免 ${2}^k$ 溢出导致误判，需要添加一个 $k > 20$ 的特判。

当 $k = 0$ 时，只有原序列有序才能在不排序的情况下有序，所以只有 $1$ 种方案。

#include<iostream>
#define ll long long
const int mod(1e9+7);
using namespace std;
ll t,n,k,jc[1000005]={0,1};
ll qpow(ll a,ll b){
	ll s=1;
	while(b){
		if(b&1) s=s*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return s;
}
int main(){
	#ifdef ytxy
	freopen("in.txt","r",stdin);
	#endif
	cin>>t;
	for(int i=2;i<=1e6;i++) jc[i]=jc[i-1]*i%mod;
	while(t--){
		cin>>n>>k;
		if(k>20||(1<<k)>=n)
			cout<<jc[n]<<'\n';
		else if(k==0)
			cout<<1<<'\n';
		else
			cout<<1ll*qpow(qpow(jc[n/(1<<k)],mod-2)/*逆元*/,1<<k)
            *qpow(qpow(n/(1<<k)+1,mod-2),n%(1<<k))%mod/*此前为求概率（所有第k层子集有序的总概率）*/
			*jc[n]/*全排列数*/%mod<<'\n'; 
	}
}