洛谷P2767 树的数量题解

题意：

求出包含 $n$ 个节点（无标号）的有根 $m$ 叉树的个数，对 $10\,007$ 取模。

两个有根树相同，当且仅当其根节点相同，且从左到右每一棵子树也相同。特别地，两个有根树均为空树，视为两个有根树相同。

输入格式：

输入两个整数 $n$ ， $m$ 。

输出格式：

输出包含 $n$ 个节点（无标号）的有根 $m$ 叉树的个数，对 $10\,007$ 取模后的值。数据范围：

$n,m \leq 127$

这题可以 $\mathcal{O}(p + \log_m n)$ 做，需要用到生成函数&拉格朗日反演。不会，可以看这篇。

这里讲 dp 的做法。

设 $f_{i,j}$ 表示 $i$ 个点，根节点有至多 $j$ 棵子树时的方案数。考虑转移

枚举点数 $k$ ，把这 $k$ 个点拆成一个新的子树算。容易发现不会算重。

f_{i, j} = i - 1 \sum k = 0 f_{k, m} \times f_{i - k, j - 1}

$f_{i,j} = \sum_{k=0}^{i-1}f_{k,m}\times f_{i-k,j-1}$

时间复杂度 $\mathcal{O}(n^3)$

代码：

cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e4+7;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x -= mod : 0; }
#define N ((int)(215))

int n,m,f[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    
    cin >> n >> m;
    for(int i=0; i<=m; i++) f[0][i] = f[1][i] = 1;
    for(int i=2; i<=n; i++)
        for(int j=1; j<=m; j++)
            for(int k=0; k<i; k++)
                add(f[i][j], f[k][m] * f[i - k][j - 1] % mod);
    cout << f[n][m] << '\n';
    return 0;
}