题目

求有多少棵严格 \(n\) 叉树深度为 \(k\)

分析

考虑往下放子孙挺难维护的，考虑在上面换新的根。

设 \(dp[i]\) 表示深度不超过 \(i\) 的方案数，那么

\(dp[i]=dp[i-1]^n+1\)

就是新开一个根，每个子节点的选择独立，为 \(dp[i-1]^n\)，再加上只有一个根节点的情况。

最后答案就是 \(dp[k]-dp[k-1]\)

代码

#include 
#include 
using namespace std;
const int N=1011; int ans[N],Ans[N],C[N],t[N],k,n;
void one(int *ans){
	int now=1;
	while (ans[now]==9) ++now;
	if (now>ans[0]) ans[0]=now;
	++ans[now];
	for (int i=1;i>=1,mul(ans,ans))
	    if (y&1) mul(t,ans);
	memcpy(ans,t,sizeof(t));
}
void dec(int *ans){
	int g=0,s;
	for (int i=1;i<=ans[0];++i){
		s=ans[i]-Ans[i]-g;
		if (s<0) g=1,ans[i]=s+10;
		    else g=0,ans[i]=s;
	}
	while (ans[0]&&!ans[ans[0]]) --ans[0]; 
}
int main(){
	scanf("%d%d",&k,&n);
	if (!n||k==1) return !printf("1");
	ans[ans[0]=1]=1;
	for (int i=1;i<=n;++i){
		memcpy(Ans,ans,sizeof(ans));
		ksm(ans),one(ans);
	}
	dec(ans);
	for (int i=ans[0];i;--i) putchar(ans[i]+48);
	return 0; 
}