BZOJ-2111: [ZJOI2010]Perm 排列计数

Description

称一个1,2,...,N的排列P1,P2...,Pn是Magic的，当且仅当2<=i<=N时，Pi>Pi/2. 计算1，2，...N的排列中有多少是Magic的，答案可能很大，只能输出模P以后的值 n<=10^6

写过手写普通堆之后一眼：这不就是构成堆的种类数吗？？？
所以说每次将最小的拿出来，然后将其余的节点分成两个集合，递归求解就好了。f[i]=f[L]*f[R]*
记忆化的话会省很多时间的吧。组合数的话直接lucas吧。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n,jc[1001000],p,f[1001000],bin[30];
int Log[1001000];
inline ll pow(ll x,ll y)
{
    ll re=1;
    while(y)
    {
        if(y&1) re=re*x%p;
        x=x*x%p; y>>=1;
    }
    return re;
}
ll C(ll x,ll y)
{
    if(y>x) return 0;
    if(x>p||y>p) return C(x/p,y/p)*C(x%p,y%p);
    return jc[x]*pow(jc[y],p-2)%p*pow(jc[x-y],p-2)%p;
}
ll solve(ll x)
{
    if(f[x]) return f[x]; int y=Log[x+1];
    if(x-1>bin[y]+bin[y-1]) return f[x]=solve(bin[y])*solve(x-1-bin[y])%p*C(x-1,bin[y])%p;
    else return f[x]=solve(bin[y-1])*solve(x-1-bin[y-1])%p*C(x-1,bin[y-1])%p;
}
int main()
{
    f[0]=f[1]=1; scanf("%lld%lld",&n,&p);
    ll cnt=1,tmp; jc[0]=1; Log[1]=0;
    for(int i=1;i<=n;++i) jc[i]=jc[i-1]*i%p;
    for(int i=2;i<=n+1;++i) Log[i]=Log[i>>1]+1;
    for(int i=0;(1ll<<i)-1<=n;++i) bin[i]=(1ll<<i)-1;
    printf("%lld",solve(n));
    return 0;
}