具体思路

挺妙的一道题。

设 $f_i$ 表示不超过 $i$ 的 $n$ 叉树的方案树。

转移方程：

答案即为 $f_d-f_{d-1}$。

设当前最大深度为 $i$，那么我们新建一个根节点，而根节点有 $n$ 个儿子。

因此每个儿子所在子树的最大深度为 $i-1$，总方案数为 $f_{i-1}$，因此 $f_i=f_{i-1}^n$。

而还有一种情况就是根节点没有儿子，所以加 $1$。

注意： 要高精度。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=33,M=4e4+5;
struct node{
	LL a[M],len;
	node(){
		len=1;
		memset(a,0,sizeof(a));
	}
}f[N];
node operator +(node n1,LL x){
	node ans=n1;
	ans.a[1]+=x;
	for(LL i=1;i<=ans.len;i++){
		ans.a[i+1]+=ans.a[i]/10;
		ans.a[i]%=10;
	}
	LL i=ans.len;
	while(ans.a[i+1]>0){
		i++;
		ans.a[i+1]+=ans.a[i]/10;
		ans.a[i]%=10;
	}
	while(i>1&&!ans.a[i])i--;
	ans.len=i;
	return ans;
}
node operator -(node n1,node n2){
	node ans;
	ans.len=n1.len;
	for(LL i=1;i<=ans.len;i++){
		ans.a[i]=n1.a[i]-n2.a[i];
	}
	for(LL i=1;i<=ans.len;i++){
		if(ans.a[i]<0){
			ans.a[i+1]--;
			ans.a[i]+=10;
		}
	}
	LL i=ans.len;
	while(ans.a[i+1]>0){
		i++;
		ans.a[i+1]+=ans.a[i]/10;
		ans.a[i]%=10;
	}
	while(i>1&&!ans.a[i])i--;
	ans.len=i;
	return ans;
}
node operator *(node n1,node n2){
	node ans;
	ans.len=n1.len+n2.len-1;
	for(LL i=1;i<=n1.len;i++){
		for(LL j=1;j<=n2.len;j++){
			ans.a[i+j-1]+=n1.a[i]*n2.a[j];
		}
	}
	LL i=ans.len;
	while(ans.a[i+1]){
		i++;
		ans.a[i+1]+=ans.a[i]/10;
		ans.a[i]%=10;
	}
	while(i>1&&!ans.a[i])i--;
	ans.len=i;
	return ans;
}
int main(){
	LL n,d;scanf("%lld%lld",&n,&d);
	if(d==0){
		puts("1");
		return 0;
	}
	f[0].a[1]=1;
	for(LL i=1;i<=d;i++){
		node ans;ans.a[1]=1;
		for(LL j=1;j<=n;j++){
			ans=ans*f[i-1];
		}
		f[i]=ans+1;
	}
	node ans=f[d]-f[d-1];
	for(LL i=ans.len;i>=1;i--){
		printf("%lld",ans.a[i]);
	}
	return 0;
}