题目描述

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

16 

HINT

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

题目分析

问题转化成：给你的数字 组成一颗小根堆的方案数
第一项为，把的两个儿子看做 和

尽管p是素数 但可能n>p 求不出逆元 所以上lucas就好了

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
long long x,p,jie[1000010],yuan[1000010];
long long f[1000010],size[1000010<<1];
void init()
{
    jie[0]=1;
    for(int i=1;i<x&&i<p;i++) jie[i]=jie[i-1]*i%p;
    yuan[0]=yuan[1]=1;
    for(int i=2;i<x&&i<p;i++) yuan[i]=(p-p/i)*yuan[p%i]%p; 
    for(int i=1;i<x&&i<p;i++) yuan[i]=yuan[i]*yuan[i-1]%p;
}
long long lucas(long long n,long long m)
{
    if(n<m) return 0;
    if(n<p&&m<p) return jie[n]%p*yuan[m]%p*yuan[n-m]%p;
    return lucas(n/p,m/p)*lucas(n%p,m%p)%p;
}
int main()
{
    scanf("%lld%lld",&x,&p);
    init();
    for(int i=x;i;i--)
    {
        size[i]=size[i<<1]+size[i<<1|1]+1;
        f[i]=lucas(size[i]-1,size[i<<1])%p*((i<<1)<=x?f[i<<1]:1)%p*((i<<1|1)<=x?f[i<<1|1]:1)%p;
    }
    printf("%lld",f[1]%p);
    return 0;
}