[BZOJ 2111] 排列计数

#include <bits/stdc++.h>

using namespace std;
#define lc (i<<1)
#define rc (i<<1|1)
typedef long long ll;
const int MAXN=1e6+10;
int sz[2*MAXN];
ll n,MOD,fac[MAXN],inv[MAXN],dp[MAXN];

ll quick_pow(ll a,ll b)
{
    ll ret=1;
    for(;b;b>>=1,a=a*a%MOD)
        if(b&1) ret=ret*a%MOD;
    return ret;
}

ll C(ll a,ll b) //n大于MOD时一定要用Lucas 
{    
    if(a<b) return 0;
    if(a<MOD&&b<MOD) return fac[a]*inv[b]%MOD*inv[a-b]%MOD;
    return C(a/MOD,b/MOD)*C(a%MOD,b%MOD)%MOD;
}

int main()
{
    scanf("%lld%lld",&n,&MOD);
    fac[0]=1;
/*    
    int mn=min(n,MOD-1); 如果n>MOD则要重新设置上限 
    for(int i=1;i<=mn;i++) fac[i]=fac[i-1]*i%MOD;
    inv[mn]=quick_pow(fac[mn],MOD-2);
    for(int i=mn-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%MOD;
*/    
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
    inv[0]=inv[1]=1;//求1-n逆元的线性做法
    for(int i=2;i<=n;i++) inv[i]=(MOD/i+1)*inv[i-MOD%i]%MOD;
    for(int i=2;i<=n;i++) inv[i]=inv[i]*inv[i-1]%MOD;
    
    for(int i=n;i>=1;i--)
    {
        sz[i]=sz[lc]+sz[rc]+1;
        dp[i]=(lc>n?1:dp[lc])*(rc>n?1:dp[rc])%MOD*C(sz[i]-1,sz[lc])%MOD;
    }
    printf("%lld",dp[1]);
    return 0;
}