Luogu

LOJ

分析

可以发现第 $i$ 个点有 $i$ 个位置可以插入，所以不同的树的个数为 $n!$，因此题目要求的就是所有树的答案总和。

如果只考虑一棵树，有一个经典的做法：考虑每个点父边的贡献，为两端点数之积 $sz \times (n - sz)$。

我们考虑枚举一个点 $i$ 和其子树大小 $k$，然后计算多少棵树中有这样的边。

首先，我们需要插入 $[1, i]$ 中的点，有 $i!$ 种方案；然后我们需要在后面的 $n - i$ 个数中选 $k$ 个并组成子树，有 ${n - 1 \choose k - 1} \times k!$ 种方法；接着考虑其后面未在 $i$ 子树中的点，这些点共有 $n - i - k + 1$ 个，依次有 $i - 1, i, \cdots$ 种选择，因此共有 $(i - 1)^{\overline{n - i - k + 1}}$ 种方法。于是可以写出答案的表达式
$$
\sum_{i = 2}^n \sum_{k = 1}^{n - i + 1} k (n - k) i! {n - 1 \choose k - 1} k! (i - 1)^{\overline{n - i - k + 1}}
$$
稍加化简得到
$$
\sum_{i = 2}^n \sum_{k = 1}^{n - i + 1} k (n - k) {n - 1 \choose k - 1} k! i (i - 1) (n - k - 1)!
$$
预处理阶乘与组合数即可 $\mathcal{O}(n^2)$ 计算。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 2000 + 10;

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

int main() {
    n = read(), mod = read();
    for (int i = C[0][0] = 1; i <= n; ++i)
        for (int j = C[i][0] = 1; j <= n; ++j)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    for (int i = fac[0] = 1; i <= n; ++i)
        fac[i] = 1ll * fac[i - 1] * i % mod;
    int ans = 0;
    for (int i = 2; i <= n; ++i)
        for (int j = 1; j <= n - i + 1; ++j)
            ans = (ans + 1ll * j * (n - j) * fac[j] % mod * C[n - i][j - 1] % mod * i * (i - 1) % mod * fac[n - j - 1]) % mod;
    printf("%d\n", ans);
    return 0;
}