Perm 排列计数（bzoj 2111）

Description

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

Input

输入文件的第一行包含两个整数 n和p，含义如上所述。

Output

输出文件中仅包含一个整数，表示计算1,2,⋯, ��的排列中， Magic排列的个数模 p的值。

Sample Input

20 23

Sample Output

HINT

100%的数据中，1 ≤ �� N ≤ 106, P�� ≤ 10^9，p是一个质数。数据有所加强

/*

    求n个数组成小根堆的方案数。

    设f[i]为以i为根的小根堆方案数。

    f[i]=C(sz[i]-1,sz[i*2])*f[i*2]*f[i*2+1]。

    最神奇的是被lucas坑了一把，当n>mod时预处理就成0啦！！！

*/

#include<iostream>

#include<cstdio>

#define N 1000010

#define lon long long

using namespace std;

int n,mod,hal[N],sz[N];

lon inv[N],jc1[N],jc2[N];

void init(){

    inv[]=inv[]=;for(int i=;i<=n;i++) inv[i]=((mod-mod/i)*inv[mod%i])%mod;

    jc1[]=;for(int i=;i<=n;i++) jc1[i]=(jc1[i-]*i)%mod;

    jc2[]=;for(int i=;i<=n;i++) jc2[i]=(jc2[i-]*inv[i])%mod;

}

lon C(int n,int m){

    if(n<m) return ;

    if(n>mod||m>mod) return (C(n%mod,m%mod)*C(n/mod,m/mod))%mod;

    else return ((jc1[n]*jc2[m])%mod*jc2[n-m])%mod;

}

void dfs1(int x){

    sz[x]=;

    if(x*<=n) dfs1(x*),sz[x]+=sz[x*];

    if(x*+<=n) dfs1(x*+),sz[x]+=sz[x*+];

}

lon dfs2(int x){

    if(x*>n) return ;

    lon tot=C(sz[x]-,sz[x*]);

    if(x*<=n) tot=(tot*dfs2(x*))%mod;

    if(x*+<=n) tot=(tot*dfs2(x*+))%mod;

    return tot;

}

int main(){

    scanf("%d%d",&n,&mod);

    init();

    dfs1();

    printf("%d",dfs2());

    return ;

}

巴特西