[HAOI2018]苹果树题解

大意:不解释

思路:

首先方案数共有n！种，第1个点只有1种选择，第2个点2种选择，生成2个选择的同时消耗一个，第3个点则有3种选择，依次类推共有n!种方案，由于最后答案*n！，故输出的实际上是每种方案的总和。

由于枚举方案是不可行的，考虑枚举边，计算每一个点连向父亲的边的贡献，容易知道贡献为siz*(n-siz)，siz为子树大小。所以枚举点与siz即可。再考虑组成子树的形态，与子树外的形态。设当前枚举到i号点，子树大小为siz，则子树内不考虑编号有siz!种形态,考虑编号则有C(n-i,siz-1)种编号组合,则子树内共有siz!*C(n-i,siz-1)种方案；考虑子树外：由于已有i个点，这i个点可以有i！种方案,从第i+siz-1点开始由于以i为根的子树siz已确定，故这个点不能插入到以i为根的子树内，所以只有i-1种选择,这一部分贡献为(i-1)*(i)*(i+1)*……*(n-siz-1)，与前面的总和化简得i*(i-1)*(n-siz-1)!。则当前枚举的点i与siz对答案的贡献为siz*(n-siz)*i*(i-1)*(n-siz-1)!*C(n-i,siz-1)*siz!。预处理出组合和阶乘枚举点i和siz统计即可。时间复杂度O(n^2);

 #include <iostream>

 #include <cstdio>

 #include <memory.h>

 #define r(x) x=read()

 #define MAXX 2005

 #define MAX(a,b) (a>b?a:b)

 #define MIN(a,b) (a<b?a:b)

 using namespace std;

 typedef long long ll;

 ll read()

 {

   char ch=;ll w=,ff=;

   while(ch<''||ch>''){if(ch=='-')ff=-;ch=getchar();}

   while(ch>=''&&ch<=''){w=w*+ch-'';ch=getchar();}

   return ff*w;

 }

 ll P,n,fac[MAXX][MAXX],jie[MAXX],ans;

 int main()

 {

   jie[]=1ll;

   r(n),r(P);

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

     for(int j=;j<=i;++j)

       fac[i][j]=(j==?:(fac[i-][j-]+fac[i-][j])%P);

   for(int i=;i<=;++i) jie[i]=jie[i-]*i*1ll%P;

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

     for(int sz=;sz<=n-i+;++sz)

       ans=(ans+(sz*1ll*(n-sz)*1ll%P*jie[sz]%P*jie[n-sz-]%P*i*(i-)%P*fac[n-i][sz-])%P)%P;

   printf("%lld",ans%P);

   return ;

 }

巴特西

[HAOI2018]苹果树题解

最新文章

热门文章