P7392 题解

_saltFish_ · 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'; 
    }
}