BZOJ 211:[ZJOI 2010]Perm配列カウント|組合せ数学|Lucas定理|DP

问题是让让1..nの小根スタックの数F[i]は、iという符号の点でスタックトップをなす合法的なスタックの数f[i]=C(size[i]−1,size[i<<1])∗f[i<<1]∗f[i<<1|1]の組合せ数をLucas定理で求めることを示す!

#include<bits/stdc++.h>
using namespace std;
int fac[1000006],inv[1000006];
int f[1000006],size[2200006];
int n,p;
void pre()
{
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(int i=2;i<=n;i++)fac[i]=1ll*fac[i-1]*i%p;
    for(int i=2;i<=n;i++)inv[i]=1ll*inv[p%i]*(p-p/i)%p;
    for(int i=2;i<=n;i++)inv[i]=1ll*inv[i-1]*inv[i]%p;
}
int C(int n,int m)
{
    if(n<m)return 0;
    if(n<p&&m<p)return 1ll*fac[n]*inv[m]%p*inv[n-m]%p;
    return 1ll*C(n/p,m/p)*C(n%p,m%p)%p;
}
int main()
{
    cin>>n>>p;
    pre();
    for(int i=n;i;i--)
    {
        size[i]=size[i<<1]+size[i<<1|1]+1;
        f[i]=1ll*C(size[i]-1,size[i<<1])*((i<<1)>n?1:f[i<<1])%p*((i<<1|1)>n?1:f[i<<1|1])%p;
    }
    cout<<f[1];
    return 0;
}