Description
如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d（根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为２的严格２元树有三个，如下图：
给出n, d，编程数出深度为d的n元树数目。
Input
仅包含两个整数n, d( 0 < n < = 32, 0 < = d < = 16)
Output
仅包含一个数，即深度为d的n元树的数目。
Sample Input1
2 2
Sample Output1
3
Sample Input2
2 3
Sample Output2
21
Sample Input3
3 5
Sample Output3
58871587162270592645034001
题解
令(f(i))表示深度小于等于(i)的严格(n)元树的总个数，则深度为(i)的严格(n)元树(f(i)-f(i-1))
分析状态转移方程，再将深度为(i-1)的树的根节点分别做一棵深度为(1)的严格(n)元树的叶子节点，再加上一个也不加的，这个总数不正是(f(i))吗？
所以状态转移方程为(f(i)=f(i-1)^n+1)，由于答案是很大的，所以要有高精度，具体见代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<bitset>
#include<map>
#include<set>
#include<queue>
#include<stack>
#define rad 1000
using namespace std;
const int D=30,L=5000;
int n,d;
struct data
{
int v[L],l;
}f[D];
data operator*(data a,data b)
{
data c;
c.l=a.l+b.l;
for(int i=1;i<=c.l;++i) c.v[i]=0;
for(int i=a.l;i;--i)
for(int j=b.l;j;--j)
c.v[i+j-1]+=a.v[i]*b.v[j];
for(int i=1;i<=c.l;++i)
if(c.v[i]>=rad)
{
if(i==c.l) ++c.l;
c.v[i+1]+=c.v[i]/rad,
c.v[i]%=rad;
}
while((c.l>1)&&(!c.v[c.l])) --c.l;
return c;
}
data operator^(data a,int b)
{
data c;
c.v[1]=1,c.l=1;
for(int i=b;i;i>>=1,a=a*a)
if(i&1) c=c*a;
return c;
}
data operator+(data a,int b)
{
a.v[1]+=b;
for(int i=1;a.v[i]>=rad;++i)
{
a.v[i+1]+=a.v[i]/rad,
a.v[i]%=rad,
a.l=max(a.l,i+1);
}
return a;
}
data operator-(data a,data b)
{
for(int i=1;i<=a.l;++i)
{
a.v[i]-=b.v[i];
if(a.v[i]<0)
{
a.v[i]+=rad,
--a.v[i+1];
}
}
while((a.l>1)&&(!a.v[a.l])) --a.l;
return a;
}
void Print(data a)
{
printf("%d",a.v[a.l]);
for(int i=a.l-1;i;--i) printf("%03d",a.v[i]);
putchar('
');
}
int main()
{
scanf("%d%d",&n,&d);
if(d==0) {puts("1");return 0;}
f[0].l=1,f[0].v[1]=1;
for(int i=1;i<=d;++i)
f[i]=(f[i-1]^n)+1;
Print(f[d]-f[d-1]);
return 0;
}