洛谷P2767 树的数量 题解
题目链接：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$ 个点拆成一个新的子树算。容易发现不会算重。
时间复杂度 $\mathcal{O}(n^3)$
代码：
#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;
}参考文献：
