题意：称一个1,2,...,N的排列P1,P2...,Pn是Magic的，当且仅当2<=i<=N时，Pi>Pi/2. 计算1，2，...N的排列中有多少是Magic的，答案可能很大，只能输出模P以后的值。
解法：我们仔细观察这个pi>=pi/2，想到什么了？像不像二叉树中每个点i和它的两个儿子的编号2i和2i+1。
那么我们可以想象每个点i想它的两个儿子2i/2i+1连边，加上Pi>Pi/2这个条件，那么这棵二叉树就是一棵小根堆。那么我们考虑用dp解决这道题，
设dp[i]表示i个不同的数组成一棵大小为i的小根堆的方案数，状态转移方程为dp[i]=C(i-1,l[i]) * dp[l[i]] * dp[r[i]] ；解释一下：这里的l[i]/r[i]代表大小为i的完全二叉树（为什么要是完全的？因为题目要求的序号是连续的）的左/右子树大小。这个方程的意思是从i-1个数里面选择l[i]个数作为左子树方案数乘以剩下r[i]个数作为右子树方案数。
那么我们预处理l[i]/r[i]就可以计算答案了。
注意此题p有可能>=n，所以要用Lucas定理计算组合数。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+;
int n,P,l[N],r[N],dp[N]; int power(int x,int p) {
int ret=;
for (;p;p>>=) {
if (p&) ret=(LL)ret*x%P;
x=(LL)x*x%P;
}
return ret;
} int fac[N],inv[N];
void prework(int n) {
fac[]=; inv[]=;
for (int i=;i<=n;i++) {
fac[i]=(LL)i*fac[i-]%P;
inv[i]=power(fac[i],P-);
}
l[]=;
for(int i=,g=;i<=n;g<<=,i+=g) {
for(int j=;j<=g;j++) l[i+j-]=l[i+j-]+;
for(int j=;j<=g;j++) l[i+g+j-]=l[i+g+j-];
}
for (int i=;i<=n;i++) r[i]=i--l[i];
} int C(int n,int m) {
if (n>=P || m>=P) return (LL)C(n/P,m/P)*C(n%P,m%P)%P;
else return (LL)fac[n]*inv[m]%P*inv[n-m]%P;
} int main()
{
cin>>n>>P;
prework(n);
dp[]=dp[]=;
for (int i=;i<=n;i++)
dp[i]=(LL)C(i-,l[i])*dp[l[i]]%P*dp[r[i]]%P;
cout<<dp[n]<<endl;
return ;
}