概要

比赛地址

2020牛客暑期多校训练营（第七场）

题目

A

B

C

D

E

F

G

H

I. Valuable Forests

前置知识：Prufer 序列

题目大意

一棵树对答案的贡献是树上每个点 i 的度的平方 d(i)^{2} 之和，一个森林对答案的贡献是所有树的贡献之和，求所有 n 个点有标号的森林的所有贡献之和。
T(T<=5000) 组样例，答案对 M 取模(1<=M<=2^{30},\ M\in prime)

分析

1. 设 dp[i] 表示 i 个点的森林的数目。考虑 dp[i] 的转移，我们令最后一个节点在一个大小为 j 的树中。由 Cayley 公式，j 个点的有标号无根树的数目为 j^{j-2}。我们从剩下的 i-1 个点中选取 j-1 个点和最后一个点处于同一棵树中：

dp[i]=\sum_{j=1}^{i}dp[i-j]\cdot C_{i-1}^{j-1}\cdot j^{j-2}

2. 设 f[i] 表示 i 个点的无根树对答案的贡献。对于这个问题，经典思想是考虑每个点的贡献。显然 i 个点对答案的贡献是一样的。
   考虑第 p 个点的贡献。枚举这个点的度数 j，由 Prufer 序列相关知识可知，i 个点树的 Prufer 序列长度为 i-2，点 p 在序列中出现的次数为 j-1。剩下的 (i-2)-(j-1)=i-j-1 个位置，由剩下 i-1 个数任意填充：

f[i]=i*\sum_{j=1}^{i-1} j^2\cdot C_{i-2}^{j-1}\cdot {(j-1)}^{i-j-1}

3. 设 ans[i] 表示题目中 i 个点森林的答案。枚举最后一个点所在树中的点的个数 j，答案被分割为两部分：前半部分的答案 ans[i-j] 乘以后半部分的数目 j^{j-2}，前半部分的数目 dp[i-j] 乘以后半部分的答案 f[j]：

ans[i]=\sum_{j=1}^{i}C_{i-1}^{j-1}\cdot \left(ans[i-j]\cdot j^{j-2}+dp[i-j]\cdot f[j]\right)

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int T, M, n;

int C[N][N], qp[N][N];
void init() {
    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 - 1] + C[i - 1][j]) % M;
        }
    }
    for (int i = 0; i < N; i++) {
        qp[i][0] = 1;
        for (int j = 1; j < N; j++) {
            qp[i][j] = 1LL * qp[i][j - 1] * i % M;
        }
    }
}

int ksm(int a, int b) {
    return b < 0 ? 1 : qp[a][b];
}

int dp[N], f[N], ans[N];
void DP() {
    dp[0] = 1;
    for (int i = 1; i < N; i++) {
        long long tmp = 0;
        for (int j = 1; j <= i; j++) {
            tmp += 1LL * dp[i - j] * C[i - 1][j - 1] % M * ksm(j, j - 2) % M;
        }
        dp[i] = tmp % M;
    }
    f[0] = f[1] = 0;
    for (int i = 2; i < N; i++) {
        long long tmp = 0;
        for (int j = 1; j <= i - 1; j++) {
            tmp += 1LL * j * j * C[i - 2][j - 1] % M * ksm(i - 1, i - j - 1) % M;
        }
        f[i] = tmp % M * i % M;
    }
    ans[0] = ans[1] = 0;
    for (int i = 2; i < N; i++) {
        long long tmp = 0;
        for (int j = 1; j <= i; j++) {
            long long x = 1LL * ans[i - j] * ksm(j, j - 2) % M + 1LL * dp[i - j] * f[j] % M;
            tmp += 1LL * C[i - 1][j - 1] * x % M;
        }
        ans[i] = tmp % M;
    }
}

int main(int argc, const char * argv[]) {
    scanf("%d%d", &T, &M);
    init();
    DP();
    while (T--) {
        scanf("%d", &n);
        printf("%d\n", ans[n]);
    }
    return 0;
}

J