[HAOI2018] 苹果树

有一棵二叉树，初态下没有结点。第一天会长出一个根结点，每个结点都有两个分叉，后面每天都会选择一个还没挂结点的分叉长出一个结点，并标上这天的时间戳。一棵树的权值为它的所有节点两两距离和。经过 (n) 天，有可能会生成 (n!) 棵不同的树，求这些树的权值和。(n leq 2000)

Solution

考虑当前已经放置了 (i) 个点

按边统计，先枚举深子树为 (j) 大小的边，然后统计它出现了多少次，每次对答案贡献为 (2j(n-j))

前 (i) 个点无限制，有 (i!) 种造法

大小为 (j) 的深子树需要从剩下的 (n-i) 个点中选出 (j) 个点造树，有 (C_{n-i}^j j!) 种造法

剩下的点不能放在上述深子树中，所以第一个点有 (i) 种放法，第二个点有 (i+1) 种放法

于是答案为

[sum_{i=1}^n sum_{j=1}^{n-i} 2j(n-j) i! C_{n-i}^j j!frac{(n-j-1)!}{(i-1)!}=sum_{i=1}^nsum_{j=1}^{n-i} 2ij(n-j)C_{n-i}^j j!(n-j-1)! ]

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 2005;

int n,mod,c[N][N],f[N],ans;

signed main() {
    cin>>n>>mod;
    f[0]=1;
    for(int i=1;i<=n;i++) f[i]=f[i-1]*i%mod;
    for(int i=0;i<=n;i++) {
        c[i][0]=1;
        for(int j=1;j<=i;j++) {
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n-i;j++) {
            ans+=2*i*j%mod*(n-j)%mod*c[n-i][j]%mod
                *f[j]%mod*f[n-j-1]%mod;
            ans%=mod;
        }
    }
    cout<<ans;
}