题目其实挺简单的,难点在于状态的设计(其实也没多难)。
令 \(f_i\) 表示 \(i\) 个点的 \(m\) 叉树的数量,发现无法转移。设 \(g_{i,j}\) 表示根节点所在子树内有 \(i\) 个节点,\(j\) 个儿子(儿子所在子树可以为空)。可以写出转移方程:\(g_{i,j}=\sum\limits_{k=0}^{i-1} g_{i-k,j-1}\times f_k\),\(f_i=f_{i,m}\)
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=200,mod=1e4+7;
int n,m,f[N][N];
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(m);
for(int i=0;i<=m;i++){
f[1][i]=f[0][i]=1;
}
for(int i=2;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<i;k++){
f[i][j]=(f[i][j]+f[i-k][j-1]*f[k][m]%mod)%mod;
}
}
}
write_endl(f[n][m]);
return 0;
}