题目传送门

题目分析

设深度恰好为 $k$ 的严格 $n$ 元树的种类数为 $f_k$。 记 $s_k=\sum_{i=1}^{k}f_i$。

考虑这个问题：现在有一个节点，如何通过在下面接深度为 $k$ 的严格 $n$ 元树使它成为深度为 $k+1$ 的严格 $n$ 元树呢？

不考虑深度是否符合要求，则它的每个子树都有 $s_k$ 种接法。因为总共有 $n$ 棵子树，故总的方案数为 $s_k^n$。

在把深度考虑进去。我们要求深度恰好为 $k$ 的，那么就是深度小于等于 $k$ 的减去深度小于 $k$ 的。深度小于 $k$ 的方案数同上可以得出为 $s_{k-1}^n$。那么我们就可以得出状态转移方程了：

$\large{f_i=s_{k-1}^n-s_{k-2}^n}$

同时统计前缀和：$s_i=s_{i-1}+f_i$。

别忘了初始值：$f_0=1$,$f_1=1$。

然后就做完啦！！！！！！！！！！！！！！！！！！！！

但是！！

答案保证不超过 $200$ 位十进制数。

所以还要手写高精！！！

AC Code

#include<iostream>
#include<vector>

namespace wyzlll // 手写高精 支持赋值加减乘快速幂输出
{
	
class lll
{
private:
	std::vector<int> a;
	void init(long long x=0)
	{
		a.clear();
		while(x)
			a.push_back(x%10),x/=10;
	}
public:
	lll(long long x=0)
	{init(x);}
	lll operator=(long long x)
	{
		init(x);
		return *this;
	}
	inline int len(){return a.size();}
	void del0()
	{
		while(a.size()&&a.back()==0)
			a.pop_back();
	}
	friend lll operator+(lll,lll);
	friend lll operator-(lll,lll);
	friend lll operator*(lll,lll);
	friend std::ostream& operator<<(std::ostream&,lll);
};
lll operator+(lll a,lll b)
{
	lll res;
	int la=a.len(),lb=b.len();
	if(la>lb) std::swap(a,b),std::swap(la,lb);
	res.a.push_back(0);
	for(int i=0;i<la;i++)
	{
		res.a[i]+=a.a[i]+b.a[i];
		res.a.push_back(res.a[i]/10);
		res.a[i]%=10;
	}
	for(int i=la;i<lb;i++)
	{
		res.a[i]+=b.a[i];
		res.a.push_back(0);
	}
	res.del0();
	return res;
}
lll operator-(lll a,lll b)
{
	lll res;
	int la=a.len(),lb=b.len();
	for(int i=0;i<lb;i++)
	{
		if(a.a[i]<b.a[i]) a.a[i]+=10,a.a[i+1]--;
		res.a.push_back(a.a[i]-b.a[i]);
	}
	for(int i=lb;i<la;i++)
		res.a.push_back(a.a[i]);
	res.del0();
	return res;
}
lll operator*(lll a,lll b)
{
	lll res;
	int la=a.a.size(),lb=b.a.size();
	for(int i=0;i<la+lb;i++) res.a.push_back(0);
	for(int i=0;i<la;i++)
		for(int j=0;j<lb;j++)
		{
			res.a[i+j]+=a.a[i]*b.a[j];
			res.a[i+j+1]+=res.a[i+j]/10;
			res.a[i+j]%=10;
		}
	res.del0();
	return res;
}
lll qpow(lll a,int b)
{
	if(!b) return 1;
	if(b==1) return a;
	lll res=qpow(a,b>>1);
	if(b&1) return res*res*a;
	return res*res;
}
std::ostream& operator<<(std::ostream &os,lll x)
{
	if(!x.len()) os<<0;
	while(x.a.size()) os<<x.a.back(),x.a.pop_back();
	return os;
}
	
}// namespace wyzlll

/*------正片开始------*/

using namespace std;
using namespace wyzlll;

lll dp[101],s[101];
void test();
int main()
{
	int n,d;
	cin>>n>>d;
	dp[0]=1,s[0]=1;
	dp[1]=1,s[1]=2;
	for(int i=2;i<=d;i++)
	{
		dp[i]=qpow(s[i-1],n)-qpow(s[i-2],n);
		s[i]=s[i-1]+dp[i];
	}
	cout<<dp[d]<<endl;
	return 0;
}

The end~

#include <bits/stdc++.h>
using namespace std;
struct node{
    int len,a[1000];
    node()
    {
        len=1;
        memset(a,0,sizeof(a));
    }
};
node operator+(node n0,int x)
{
    n0.a[1]+=x;
    for(int i=1;i<=n0.len;i++)
    {
        n0.a[i+1]+=n0.a[i]/10;
        n0.a[i]%=10;
    }
    int i=n0.len;
    while(n0.a[i+1]>0)
    {
        i++;
        n0.a[i+1]+=n0.a[i]/10;
        n0.a[i]%=10;
    }
    while( (n0.a[i]==0) && (i>1) ) i--;
    n0.len=i;
    return n0;
}
node operator-(node n1,node n2) 
{
    for(int i=1;i<=n1.len;i++)n1.a[i]-=n2.a[i];
    for(int i=1;i<=n1.len;i++)
    { 
        if(n1.a[i]<0) 
        {
            n1.a[i]+=10;
            n1.a[i+1]--;
        }
    }
    while(n1.a[n1.len]==0 && n1.len>1) n1.len--;
    return n1;
}
node operator*(node n1,node n2)
{
    node no;
    no.len=n1.len+n2.len-1;
    for(int i=1;i<=n1.len;i++)for(int j=1;j<=n2.len;j++)no.a[i+j-1]+=n1.a[i]*n2.a[j];
    for(int i=1;i<=no.len;i++)
    {
        no.a[i+1]+=no.a[i]/10;
        no.a[i]%=10;
    }
    int i=no.len;
    while(no.a[i+1]>0)
    {
        i++;
        no.a[i+1]+=no.a[i]/10;
        no.a[i]%=10;
    }
    while((no.a[i]==0)&&(i>1)) i--;
    no.len=i;
    
    return no;
}
int main()
{
    int n,d;cin >>n>>d;
    if(d==0) { printf("1");return 0;}
    f[0].a[1]=1;
    for(int i=1;i<=d;i++)
    {
        f[i].a[1]=1;
        for(int j=1;j<=n;j++)f[i]=f[i]*f[i-1];
        f[i]=f[i]+1;
    }
    node ans=f[d]-f[d-1];
    for(int i=ans.len;i>=1;i--)printf("%d",ans.a[i]);
    return 0;
}