Sengxian's Blog

题目地址

描述

请你计算含有 $n(1\le n\le 1000)$ 个点的不同构的树数量，满足内部节点（度数大于 1）的度数均为 $d(1\le d\le 10)$。

分析

我们先计算不同构的有根树，至于怎么保证不同构，我们稍后再说。
设 $f(i, j, k)$ 为不同构的有根树的数量，满足树的大小为 $i$，其根有 $j$ 个子树，其中每个子树的大小都不超过 $k$，除了根以外，内部节点满足度数为 $d$ 的限制。
我们先考虑下转移，再来考虑边界。对于 $f(i, j, k)$，分两种情况考虑：

1. 不存在大小为 $k$ 的子树，这就是 $f(i, j, k - 1)$。
2. 存在 $t > 0$ 个大小为 $k$ 的子树，我们枚举 $t$，首先子树小于 $k$ 的部分就是 $f(i - t\cdot k, j - t, k - 1)$，接着还需要加入 $t$ 个大小为 $k$ 的子树，大小为 $k$ 的子树有 $f(k, d - 1, k - 1)$ 个，设 $m = f(k, d - 1, k - 1)$，我们需要计算 这样的 $m$ 元组的数量，其中 $x_i$ 表示选择第 $i$ 种树的数量，而且有 。可用组合数学中经典的隔板法求解，数量为 $\binom{f(k, d - 1, k - 1) + t - 1}t$。

这样就得到转移：

通过这样的转移，我们无需担心将同构的树计算两次。对于第一种情况可根据归纳法得到，而对于第二种情况，如果将根的所有子树视作一个多重集合的话，如果我们将每个集合都被能计数且仅计数一次，那么就能保证正确性。首先对于不同的 $t$，被计数的子树集合肯定是不同的，所以只需考虑单个 $t$。而对于一个确定的 $t$，被计数的集合中又分为了两部分，第一部分为大小小于 $k$ 的子树，这一部分由于是用的其他的状态，所以可以用归纳法得到正确性，现在我们只需要保证第二部分是正确的就行了（因为子树集合之间没有交集，所以相乘起来仍然是正确的）；而第二部分为大小等于 $k$ 的子树，我们发现对于每个子树集合，都能唯一对应一个 $m$ 元组 ，由于我们用隔板法得到的解是不重不漏的，所以第二部分也是正确的。这样就完成了不同构的有根树的证明。

现在我们需要计算无根不同构的树的数量，我们将每棵树的重心当作根（好处就是每棵树至多有 2 个重心，不可能没有重心，详情见 Centered tree）。所有符合条件的树中，只有一个重心的树的数量为：$f(n, d - 1, \lceil\frac n 2\rceil - 1)$，其中 $\lceil\frac n 2\rceil - 1$ 是要保证只存在一个重心，只限制为 $\lfloor\frac n 2\rfloor$ 是不够的（长度为 4 的链就是一个直接的反例）。有两个重心的树，必然满足 $n$ 为偶数，否则不存在。如果有两个重心，其两个重心必定是相邻的，如果我们去掉连接他们的边，会得到 2 个大小为 $\frac n 2$ 的联通块，这样我们就可以得到数量：$\binom {f(\frac n 2, d - 1, \frac n 2 - 1) + 1} 2$，还是运用了隔板法来计算合法二元组个数。

最后谈谈边界，$f(1, 0, 0) = 1$，这个是一个节点做根的情况；题目中要求内部节点的度数都为 $d$，那么谁是非内部节点呢？叶子，因为叶子的度数总是为 1，所以我们将叶子的度数给为 $d - 1$，即 $f(1, d - 1, 0) = 1$，这个是单个节点做叶子的情况，因为连这个叶子就可以满足此叶子度数为 $d$。

利用吸收不等式：

就可以通过递推来得到每次的组合数，总的复杂度：$O(n^2\cdot d^2)$。

代码

//  Created by Sengxian on 2016/10/10.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Codeforces 724F 树的计数（不同构）
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAX_N = 1000 + 3, MAX_D = 10 + 3;
int n, d, modu, dp[MAX_N][MAX_D][MAX_N];
int inv[MAX_N];

inline ll mod_pow(ll a, int b) {
    ll res = 1;
    while (b) {
        if (b & 1) (res *= a) %= modu;
        (a *= a) %= modu;
        b >>= 1;
    }
    return res;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    scanf("%d%d%d", &n, &d, &modu);
    if (n <= 2) return puts("1"), 0;
    for (int i = 1; i < n; ++i) inv[i] = mod_pow(i, modu - 2);
    dp[1][0][0] = dp[1][d - 1][0] = 1;
    for (int i = 2; i <= n; ++i)
        for (int j = 1; j <= d; ++j)
            for (int k = 1; k < i; ++k) {
                dp[i][j][k] = dp[i][j][k - 1];
                int r = dp[k][d - 1][k - 1] - 1, c = 1;
                for (int t = 1; t * k < i && t <= j; ++t) {
                    c = (ll)c * (++r) % modu * inv[t] % modu;
                    (dp[i][j][k] += (ll)dp[i - t * k][j - t][min(k - 1, i - t * k - 1)] * c % modu) %= modu;
                }
            }
    ll ans = dp[n][d][(n + 1) / 2 - 1];
    if (n % 2 == 0) ans += (ll)(dp[n / 2][d - 1][n / 2 - 1]) * (dp[n / 2][d - 1][n / 2 - 1] + 1) / 2;
    ans %= modu;
    cout << ans << endl;
    return 0;
}