题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

20 23

输出样例#1：

16

说明

100%的数据中，1 ≤N ≤ 10^6, P≤ 10^9，p是一个质数。

题解

题目就是让你求出有多少种排列满足小根堆

由于每个点的限制条件构成了一颗二叉树

所以我们可以设f[i]表示以值i为根的小根堆的数目

那么显然ta的子树内的所有取值都要比他大

所以我们可以统计出它及它的子树有多少大Num[i]

这样\(f[i] =C(Num[i],Num[ls])*f[ls]*f[rs]\)就可以转移了

因为到i时有Num[i]个值待选

那么分配Num[ls]个值给左子树的方案数乘上f[ls]和f[rs]就是f[i]了

#include
    
     #include
     
      #include
      
       #include
       
        const int M = 1000005 ;using namespace std ;int n , mod ;int f[M] , fac[M] , Num[M] ;inline int fpw(int Base , int k) {    int temp = 1 ;    while(k) {        if(k & 1) temp = (1LL * temp * Base) % mod ;        Base = (1LL * Base * Base) % mod ; k >>= 1 ;    }    return temp ;}inline int C(int n , int m) {    return (1LL * fac[n] % mod * fpw((1LL * fac[m] * fac[n - m]) % mod , mod - 2) % mod) % mod ;}int main() {    cin >> n >> mod ;    fac[0] = 1LL ;    for(int i = 1 ; i <= n ; i ++) fac[i] = (1LL * fac[i - 1] * i) % mod ;    for(int i = n ; i >= 1 ; i --) {        Num[i] = 1 ;        if(i * 2 <= n) Num[i] += Num[i << 1] ;        if(i * 2 + 1 <= n) Num[i] += Num[i << 1 | 1] ;        if(i * 2 + 1 <= n) f[i] = (1LL * C(Num[i] - 1 , Num[i << 1]) * f[i << 1] % mod * f[i << 1 | 1]) % mod ;        else if(i * 2 <= n) f[i] = f[i << 1] ;        else f[i] = 1 ;    }    cout << f[1] << endl ;    return 0 ;}