Description：

计算深度为 $d$ 每个非叶子节点都有恰好 $n$ 个儿子的树的个数。

$1\le n \le 32,1\le d \le 16$

Solution：

给叶子加点的做法是行不通的，考虑给根节点加儿子，根节点如果有儿子一定有 $n-1$ 个儿子，每个儿子的最大深度为 $d-1$ ，于是设 $f[i]$ 表示深度 $\le i$ 的 $n$ 元树的个数，转移为 $f[i]=f[i-1]^n+1$ ，加一是因为还可以根节点没有儿子，最后答案就是 $f[i]-f[i-1]$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,d;

#define MAXD 17

struct bigint

{

	int len,m[410];

	bigint(){len = 0;memset(m,0,sizeof(m));}

	friend bigint operator + (bigint a,int b)

	{

		a.m[1] += b;

		for(int i = 1;i <= a.len;++i)

		{

			if(a.m[i] < 10)break;

			a.m[i + 1] += a.m[i] / 10;

			a.m[i] %= 10;

		}

		if(a.m[a.len + 1] > 0)++a.len;

		return a;

	}

	friend bigint operator * (bigint a,bigint b)

	{

		bigint c;

		c.len = a.len + b.len - 1;

		for(int i = 1;i <= a.len;++i)

			for(int j = 1;j <= b.len;++j)

				c.m[i + j - 1] += a.m[i] * b.m[j];

		for(int i = 1;i <= c.len;++i)

		{

			c.m[i + 1] += c.m[i] / 10;

			c.m[i] %= 10;

		}

		if(c.m[c.len + 1] > 0)++c.len;

		return c;

	}

	friend bigint operator ^ (bigint a,int b)

	{

		bigint res;res = res + 1;

		while(b > 0)

		{

			if(b & 1)res = res * a;

			a = a * a;

			b = b >> 1;

		}

		return res;

	}

	friend bigint operator - (bigint a,bigint b)

	{

		for(int i = 1;i <= b.len;++i)

			a.m[i] -= b.m[i];

		for(int i = 1;i <= a.len;++i)

		{

			if(a.m[i] < 0)

			{

				a.m[i] += 10;

				a.m[i + 1] -= 1;

			}

		}

		while(a.m[a.len] == 0)--a.len;

		return a;

	}

}f[MAXD];

void print(bigint d)

{

	for(int i = d.len;i >= 1;--i)

	{

		cout << d.m[i];

	}

	cout << endl;

	return;

}

int main()

{

	scanf("%d%d",&n,&d);

	f[0] = f[0] + 1;

	for(int i = 1;i <= d;++i)

	{

		f[i] = (f[i - 1] ^ n) + 1;

	}

	print(f[d] - f[d - 1]);

	return 0;

}