P2767 树的数量

· · 题解

题意

求 n 个节点的有根 m 叉树的个数

题解

其他题解里写的神仙组合数看不懂，发个 O(n^3) 的动规题解吧

好想又好写，动规大法保智商

状态
###### 转移 先强势上图 ![](https://cdn.luogu.com.cn/upload/image_hosting/jet6pd0f.png) $$dp_{i,j}=\sum_{k=0}^{i-1}dp_{k,m}\cdot dp_{i-k,j-1}$$ 我们枚举当前的这棵子树有 $k$ 个点，允许有空树，所以 $k\ge 0$，要给根节点留一个点，所以 $k\le i-1$，这棵子树允许最多有 $m$ 个儿子，所以该子树的方案数为 $dp_{k,m}

现在还剩下一颗有 i-k 个节点的树，因为有一个子树配额被我们枚举的子树用掉了，所以现在还有 j-1 个子树配额，剩下的树的方案数为 dp_{i-k,j-1}

把两个柿子乘一乘加一加就得到 dp_{i,j} 了

代码

#include<iostream>
#define mod 10007
using namespace std;
int n,m,dp[128][128];
int main()
{
    cin>>n>>m;
    for(int i=0;i<=m;i++)dp[0][i]=1;
    for(int i=0;i<=m;i++)dp[1][i]=1;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k<i;k++)
                dp[i][j]=(dp[i][j]+dp[k][m]*dp[i-k][j-1]%mod)%mod;
    cout<<dp[n][m];
}