Description
Link.
给定三个数 (n,d,mod)，求有多少种 (n) 个点的不同构的树满足：除了度数为 (1) 的结点外，其余结点的度数均为 (d)。答案对质数 (mod) 取模。
Solution
感觉这个题好神啊，看 Editorial 看了半天。
先考虑 rooted 情况。设 (f(i,j,k)) 为有 (i) 个结点，当前根有 (j) 棵 subtree，最大的子树大小不超过 (k) 的答案，字数内的结点的度数皆为 given (d)（除了当前根本身）。
转移即：
[f(i,j,k)=f(i,j,k-1)+left(sum_{l=1}^{lle d,k imes l<i}f(i-k imes l,j-l,k-1) imesinom{f(k,d-1,k-1)+l-1}{l}
ight)
]
意义我就直接 copy CSDN@forever_shi 了：
解释一下这个式子，就是你子树大小不超过 (k) 的可以从都不超过 (k−1) 的转移过来，然后我们可以之前子树都是不超过 (k−1)，现在开始是不超过 (k) 的了，也就是在当前选了若干个大小是 (k) 的子树，而这几个是一个可重组合，于是乘那个组合数。
#include<bits/stdc++.h>
typedef long long LL;
int n,d,MOD,far[1010],exfar[1010],f[1010][20][1010];
void exGCD(int one,int ano,int &x,int &y)
{
if(ano==0)
{
x=1;
y=0;
}
else
{
exGCD(ano,one%ano,y,x);
y-=(one/ano)*x;
}
}
int inv(int val)
{
int res,w;
exGCD(val,MOD,res,w);
return (res%MOD+MOD)%MOD;
}
int C(int n,int k)
{
if(n<k) return 0;
else
{
int res=1;
for(int i=1;i<=k;++i) res=LL(res)*(n-i+1)%MOD;
return LL(res)*exfar[k]%MOD;
}
}
int main()
{
scanf("%d %d %d",&n,&d,&MOD);
if(n<=2)
{
printf("1
");
return 0;
}
far[0]=exfar[0]=1;
for(int i=1;i<=d;++i) far[i]=LL(far[i-1])*i%MOD;
for(int i=1;i<=d;++i) exfar[i]=inv(far[i]);
for(int i=0;i<=n;++i) f[1][0][i]=1;
for(int i=2;i<=n;++i)
{
for(int j=1;j<i && j<=d;++j)
{
for(int k=1;k<=n;++k)
{
f[i][j][k]=f[i][j][k-1];
for(int l=1;l*k<i && l<=j;++l)
{
if(k>1) f[i][j][k]=(f[i][j][k]+LL(f[i-k*l][j-l][k-1])*C(f[k][d-1][k-1]+l-1,l)%MOD)%MOD;
else f[i][j][k]=(f[i][j][k]+LL(f[i-k*l][j-l][k-1])*C(f[k][0][k-1]+l-1,l)%MOD)%MOD;
}
}
}
}
if(n&1) printf("%d
",f[n][d][n>>1]);
else printf("%d
",(f[n][d][n>>1]-C(f[n>>1][d-1][n>>1],2)+MOD)%MOD);
return 0;
}