解题：HAOI2018 苹果树

时间：2024-05-25 20:32:50

题面

统计贡献，每个大小为i的子树贡献就是$i(n-i)$，然后子树里又有$i!$种；同时这个子树的根不确定，再枚举这个根是$r$个放的，又有了$r!$种。子树内选点的方式因为子树的根被钦定了顺序所以只有一个组合数，子树外面的则是一个连乘积。答案就是

$i(n-i)i!r!C_{n-r}^{i-1}\prod\limits_{j=r-1}^{n-i-1}j$

$=(r-1)r*i*i!*(n-i)!$

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 int n,mod,ans,fac[N],C[N][N];

 void Add(int &x,int y)

 {

     x+=y;

     if(x>=mod) x-=mod;

 }

 void exGCD(int a,int b,int &x,int &y)

 {

     if(!b) x=,y=;

     else exGCD(b,a%b,y,x),y-=a/b*x;

 }

 int Inv(int x)

 {

     int xx,yy;

     exGCD(x,mod,xx,yy);

     return (xx%mod+mod)%mod;

 }

 void Pre()

 {

     fac[]=;

     for(int i=;i<=n;i++) fac[i]=1ll*fac[i-]*i%mod;

     for(int i=;i<=n;i++) C[i][]=;

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

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

             C[i][j]=(C[i-][j-]+C[i-][j])%mod;

 }

 int main()

 {

     scanf("%d%d",&n,&mod),Pre();

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

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

             Add(ans,(1ll*(i-)*i*j%mod)*(1ll*fac[j]*fac[n-j]%mod)%mod*C[n-i][j-]%mod);

     printf("%d",ans);

     return ;

 }

相关文章