有一个显然的套路
(i)的父边对总距离和贡献为(siz_i(n-siz_i))
在序列问题中有一个非常常见的套路是取任意一个“分割点”然后分别考虑分割点左边和右边的情况,两个乘起来就是我们要求的序列个数
同理我们在树上也可以采取类似的套路,删掉一条边,考虑分开的两个联通块的方案数,两个乘起来就是合法树的个数了
考虑(i)子树的情况,从形态讲,树一共会有(siz_i!)种不同形态,从树点编号讲,一共有(large {siz_i-1choose n-i})种编号,已经选了(n-i)个点,选了(i),再选(siz_i-1)
因为要从上向下生成树,所以保证子树点编号比(i)大来满足,所以子树方案数(large siz_i!{siz_i-1choose n-i})
考虑子树外的情况
生成(i)之前共(i!)种不同方式,生成(i)后是不可将点放在(i)子树中,后面的点有((i+1-2),(i+2-2),(i+3-2)...(n-siz_i+1-2))的生成方式
化简(i(i-1)(n-siz_i-1)!)
子树外的方案(large siz_i!{siz_i-1choose n-i}i(i-1)(n-siz_i-1)!)
总方案
[sum_{i=2}^nsum_{siz=1}^{n-i+1}siz_i!{siz_i-1choose n-i}i(i-1)(n-siz_i-1)!
]
const int N = 2005;
ll mod,dp[N][N],fac[N],c[N][N],res;int n;
int main(){
scanf("%d%lld",&n,&mod);fac[0] = 1; dp[1][1] = 1;
for(int i = 0;i <= n;++i) c[i][i] = c[0][i] = 1;
for(int i = 0;i <= n;++i)
for(int j = 1;j < n;++j)
c[j][i] = (c[j-1][i-1] + c[j][i-1]) % mod;
for(int i = 1;i <= n;++i) fac[i] = fac[i-1] * i % mod;
for(int i = 2;i <= n;++i)
for(int j = 1;j <= i;++j)
dp[i][j] = fac[i-2] * j % mod * (j-1) % mod;
for(int i = 2;i <= n;++i)
for(int j = 1;j <= n-i+1;++j)
(res += fac[j]*c[j-1][n-i]%mod*j*(n-j)%mod*dp[n-j+1][i]) %= mod;
printf("%lld",res);
}