洛谷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\) 个点拆成一个新的子树算。容易发现不会算重。
\[ f_{i,j} = \sum_{k=0}^{i-1}f_{k,m}\times f_{i-k,j-1} \] 时间复杂度 \(\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;
}参考文献：
