Codeforces 724F - Uniformly Branched Trees

Published on 2016-10-10

题目地址

描述

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

分析

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

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

这样就得到转移:

f(i,j,k)=f(i,j,k1)+t>0f(itk,jt,k1)(f(k,d1,k1)+t1t)f(i, j, k) = f(i, j, k - 1) + \sum_{t>0}f(i - t\cdot k, j - t, k - 1)\cdot\binom{f(k, d - 1, k - 1) + t - 1}t

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

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

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

利用吸收不等式:

就可以通过递推来得到每次的组合数,总的复杂度:O(n2d2)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;
}