[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]]$$

然后实现即可

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 typedef long long L;

 L n,p;

 L fac[];

 inline L po(L x,L hm){

     L ret();

     while(hm){

         if(hm&)

             ret=ret*x%p;

         x=x*x%p;

         hm>>=;

     }

     return ret;

 }

 inline L C(int n,int m){

     return fac[n]*po(fac[m],p-)%p*po(fac[n-m],p-)%p;

 }

 struct edge{

     int e;

     edge *n;

 }a[],*pre[];

 int tot;

 inline void insert(int s,int e){

     a[++tot].e=e;

     a[tot].n=pre[s];

     pre[s]=&a[tot];

 }

 int size[];

 inline void get_size(int u){

     size[u]=;

     for(edge *i=pre[u];i;i=i->n){

         int e(i->e);

         if(!size[e]){

             get_size(e);

             size[u]+=size[e];

         }

     }

 }

 L f[];

 inline void dfs(int u){

     if(u>n){

 //      size[u]=0;

 //      f[0]=1;

         return;

     }

 //  cout<<u<<endl;

 //  size[u]=1;

     dfs(u<<);

 //  size[u]+=size[u<<1];

     dfs(u<<|);

 //  size[u]+=size[u<<1|1];

     f[size[u]]=C(size[u]-,size[u<<])*f[size[u<<]]%p*f[size[u<<|]]%p;

 }

 inline int gg(){

 //  freopen("permzj.in","r",stdin);

 //  freopen("permzj.out","w",stdout);

     scanf("%lld%lld",&n,&p);

     fac[]=fac[]=;

     for(int i=;i<=n;++i){

         L tmp(i);

         while(tmp%p==)

             tmp/=p;

         fac[i]=fac[i-]*tmp%p;

     }

     for(int i=;i<=n;++i){

         if((i<<)>n)

             break;

         insert(i,i<<);

         if((i<<|)>n)

             break;

         insert(i,i<<|);

     }

     get_size();

     f[]=f[]=;

     dfs();

     printf("%lld",f[n]%p);

 //  for(int i=1;i<=n;++i)

 //      cout<<"i="<<i<<" size[i]="<<size[i]<<endl;

     return ;

 }

 int K(gg());

 int main(){;}

巴特西

[ZJOI2010]Perm

[ZJOI2010]Perm

题目

INPUT

OUTPUT

SAMPLE

INPUT

OUTPUT

解题报告

最新文章

热门文章