排列计数

望眼浮云 · 2018-07-10 19:58:17 · 题解

Pi>Pi/2.可以转换为

Pi>P2i(i≤n/2)

Pi>P2i+1(i<n/2)

想到了什么？

在一棵树里，i的左孩子为2×i，右孩子为2×i+1

所以我们可以构造一个大根堆

我们只需要在这棵树中填写数字就好了。

以n=10为例，设f[x]为答案

f[10]=C(9,6)×f[6]×f[3] //结点1填10，左子树有6个点，从9个数中取6个填入，再乘f[6]×f[3];

   =C(9,6)×C(5,3)×f[3]×f[2]×C(2,1)
   =C(9,6)×C(6,3)×C(2,1)×C(2,1)
   =3360

#include<cstdio>
using namespace std;
typedef long long LL;
const LL p=1e9+7;  
LL n,a[100000],f[100000],jc[100000],i,k; //a[i]记录以i为结点的子树的结点个数
LL pow(LL a,LL b,LL p){   //快速幂求逆元
    LL ans=1;   
    while(b){
        if(b&1) ans=ans*a%p;    
        b>>=1;  
        a=a*a%p;
    }   
    return ans;
}
LL get_answer(LL k,int l) //l为当前结点编号，k为a[l]
{
    if(k==1||k==0) return 1;  
    if(k==2) return 1;
    if(k==3) return 2;
    int u=a[l*2],v=a[l*2+1]; 
    if(f[u]==0) f[u]=get_answer(u,l*2); //递归求左子树
    if(f[v]==0) f[v]=get_answer(v,l*2+1); //递归求右子树
    return jc[k-1]*pow(jc[u],p-2,p)%p*pow(jc[k-1-u],p-2,p)%p*f[u]%p*f[v]%p;
}
int main()
{
    scanf("%lld",&n);
    for(i=1;i<=n;i++){  //填a[i]
        k=i;
        while(k!=0) a[k]++,k/=2;
    }
    jc[0]=jc[1]=1;
    for(i=1;i<=n;i++) jc[i]=jc[i-1]*i%p; //预处理阶乘
    printf("%lld",get_answer(n,1));
    return 0;
}