题目链接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=2111

题意：求1到n有多少种排列满足:A[i]>A[i/2](2<=i<=n)。

思路：形式类似二叉树。建模之后其实就是n个节点的不同的满二叉树有多少种？用f[i]表示i个节点的满二叉树个数，则f[n]=f[L]*f[R]*C(n-1,L)。其中L和R对于确定的n来说是确定的。比如n=10时，左右子树分别有6、3个点。

 

i64 a[N],n,p,f[N];void init(){    int i;    a[0]=1;    FOR1(i,N-1) a[i]=a[i-1]*i%p;}i64 exGcd(i64 a,i64 b,i64 &x,i64 &y){    if(b==0)    {        x=1;        y=0;        return a;    }    i64 temp=exGcd(b,a%b,x,y);    i64 t=x;    x=y;    y=t-a/b*y;    return temp;}i64 reverse(i64 a){    i64 x,y;    exGcd(a,p,x,y);    x=(x%p+p)%p;    return x;}i64 C(i64 n,i64 m){    return a[n]*reverse(a[m]*a[n-m]%p)%p;}int get(int x){    if(x==1) return 1;    int i;    for(i=1;;i++)    {        x-=(1<