B. Perm 排列计数
内存限制：512 MiB 时间限制：1000 ms 标准输入输出
题目描述
称一个1,2,...,N的排列P1,P2...,Pn是Magic的，当且仅当2<=i<=N时，Pi>Pi/2. 计算1，2，...N的排列中有多少是Magic的，答案可能很大，只能输出模P以后的值
输入格式
输入文件的第一行包含两个整数 n和p，含义如上所述。
输出格式
输出文件中仅包含一个整数，表示计算1,2,?, ???的排列中， Magic排列的个数模 p的值。
样例
样例输入
20 23样例输出
16数据范围与提示
100%的数据中，1 ≤ ??? N ≤ 106, P??? ≤ 10^9，p是一个质数。 数据有所加强
题解
刚拿到这道题的时候没什么思路，但脑子啊有时候吧～～
可以把这个题想象成一棵二叉树，下标即在排列中的位置，当然1为根
一个点的任意一个子孙一直除2的话最终都会到该点，即在以该点为根的子树内，该点值最小
假设有n个点，父亲要最小的那一个，左右儿子各自成家，互不干扰，左儿子要剩下的n-1个中的m个，剩下的都给了右儿子一家，组合数为C(n-1,m),向下一个个分下去你会发现
转移式为 f[爹]=f[左儿子]*f[右儿子]*C(size[],size[]) f[]表示满足条件的组合数，size[]表示以该点为根的树的大小
因为n有点大，n!会炸掉，所以求组合数的时候上Lucas定理就欧了
弱弱的Lockey死活不用Lucas（我牛逼，我伟大），一直在搞高精乘低精，高精除低精，但还是在强悍的Lucas面前献上了膝盖%%%%
#include<iostream>
#include<cstdio>
using namespace std;
int n,p,son[],d[];
long long ans=;
long long pow(long long a,long long b,long long p){
long long ans=;
a%=p;
while(b){
if(b&) ans=(ans*a)%p;
b>>=;
a=(a%p)*(a%p)%p;
}
ans%=p;
return ans;
}
long long inv(long long x,long long p){
return pow(x,p-,p);
}
long long C(long long n,long long m){
if(m>n) return ;
long long up=,down=;
for(int i=n-m+;i<=n;i++) up=up*i%p;
for(int i=;i<=m;i++) down=down*i%p;
return up*inv(down,p)%p;
}
long long Lucas(long long n,long long m,long long p){
if(m==) return ;
return C(n%p,m%p)*Lucas(n/p,m/p,p);
}
void dfs(int x){
if(*x<=n) dfs(*x);
if(*x+<=n) dfs(*x+);
son[x]=son[*x]+son[*x+]+;
if(son[x]>){
ans=(long long)(ans%p)*(long long)(Lucas(son[x]-,son[*x]?son[*x]:son[*x+],p)%p)%p;
}
return;
}
int main(){
scanf("%d%d",&n,&p);
if(n==){
cout<<%p;
return ;
}
dfs();
cout<<ans%p;
}