[ZJOI2010]Perm

题目

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

INPUT

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

OUTPUT

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

SAMPLE

INPUT

20 23

OUTPUT

16

解题报告

这竟然是一道树规= =

其实想明白之后挺简单的

我们考虑一颗满二叉树，一个节点$i$如果有左儿子，那么它的左儿子编号一定为$i\times 2$，如果它有右儿子，那么它的右儿子编号一定为$i\times 2+1$

再回来看这道题，假如我们建一颗满二叉树，那么问题不就转化成所有儿子的权值都比父亲的权值大的方案数么？

设$f[size[i]]$代表编号为$i$的节点的方案数

我们要取出$i-1$个（把自己去掉）比它大的数，一部分放在左子树，一部分放在右子树，且当左子树确定了取出哪些数时，右子树所取出的数也是一定的

故我们可以推出状态转移方程：

$$f[size[i]]=C_{size[i]-1}^{size[i<<1]}\times f[size[i<<1]]\times f[size[i<<1|1]]$$

然后实现即可

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 typedef long long L; 6 L n,p; 7 L fac[1000005]; 8 inline L po(L x,L hm){ 9     L ret(1);10     while(hm){11         if(hm&1)12             ret=ret*x%p;13         x=x*x%p;14         hm>>=1;15     }16     return ret;17 }18 inline L C(int n,int m){19     return fac[n]*po(fac[m],p-2)%p*po(fac[n-m],p-2)%p;20 }21 struct edge{22     int e;23     edge *n;24 }a[1000005],*pre[1000005];25 int tot;26 inline void insert(int s,int e){27     a[++tot].e=e;28     a[tot].n=pre[s];29     pre[s]=&a[tot];30 }31 int size[2000005];32 inline void get_size(int u){33     size[u]=1;34     for(edge *i=pre[u];i;i=i->n){35         int e(i->e);36         if(!size[e]){37             get_size(e);38             size[u]+=size[e];39         }40     }41 }42 L f[2000005];43 inline void dfs(int u){44     if(u>n){45 //      size[u]=0;46 //      f[0]=1;47         return;48     }49 //  cout<
         <
          
           n)70             break;71         insert(i,i<<1);72         if((i<<1|1)>n)73             break;74         insert(i,i<<1|1);75     }76     get_size(1);77     f[0]=f[1]=1;78     dfs(1);79     printf("%lld",f[n]%p);80 //  for(int i=1;i<=n;++i)81 //      cout<<"i="<
           <<" size[i]="<
            
             <