题干：
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,⋯, n的排列中， Magic排列的个数模 p的值。
Sample Input
20 23
Sample Output
16
HINT
100%的数据中，1 ≤ N ≤ 106, P≤ 10^9，p是一个质数。
题目概述：求N个数的排列中满足P[i]>P[i/2]的个数。
题解：
拿到这道题一脸懵比，自己想了半天妄图用纯组合数学知识做出来。
问了问大佬，大佬说要用小根堆，吓得我直接就不是人了。
研究了一下，发现这道题其实就是求n个数组成的小根堆的个数。
写出来一个状态转移方程（搞得跟树归似的吓死个人）：f[i]=f[i<<1]+f[i<<1|1]+C(size[i-1],size[i<<1]);
解释一下：上式中，size代表小根堆（其实就是一个树型的）以某一点为根节点的子树的大小。
f代表以当前节点为根节点的小根堆共有多少中排列方式。
$C_{size[i-1]}^{size[i<<1]}$代表的意义是：从比i大的数字中选出左儿子需要的个数插入到左子树中组成的一种排列。
其实$C_{size[i-1]}^{size[i<<1]}$和$C_{size[i-1]}^{size[i<<1|1]}$还是一样的。
size的累加过程：siz[i]=siz[i<<1]+siz[i<<1|1]+1;
我们发现，n的范围还是不小的（10的6次方），所以用到了Lucas定理。就这样啦～
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<cmath> #include<cstdlib> using namespace std; long long n,p,siz[4000006],dp[4000006]; long long fac[40000006]; inline long long qpow(long long a,long long b) { register long long ans=1; a%=p; while(b) { if(b&1) ans=ans*a%p; a=a*a%p; b>>=1; } return ans; } inline long long C(long long nn,long long k) { if(k>nn)return 0; else return fac[nn]*(qpow(fac[k]*fac[nn-k]%p,p-2))%p; } inline long long Lucas(long long a,long long b) { if(b==0) return 1; return C(a%p,b%p)*Lucas(a/p,b/p)%p; } inline void getchart() { fac[1]=fac[0]=1; for(register long long i=2;i<=n;i++) fac[i]=(fac[i-1]*i)%p; return ; } int main() { scanf("%lld %lld",&n,&p); getchart(); // cout<<fac[10]<<endl; for(register int i=n;i>=1;--i) { siz[i]=siz[i<<1]+siz[i<<1|1]+1; dp[i]=Lucas(siz[i]-1,siz[i<<1]); if((i<<1)<=n) dp[i]=(dp[i]*dp[i<<1])%p; if((i<<1|1)<=n) dp[i]=(dp[i]*dp[i<<1|1])%p; } printf("%lld ",dp[1]); return 0; }