十几年前的题啊……果然还处于高精度遍地走的年代。不过通过这道题，小C想mark一下n叉树计数的做法。
Description
如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d（根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为2的严格2元树有三个，如下图：
给出n,d，编程数出深度为d的n元树数目。
Input
仅包含两个整数n,d。
Output
仅包含一个数，即深度为d的n元树的数目。
Sample Input
3 5
Sample Output
58871587162270592645034001
HINT
0 < n <= 32，0 <= d <=16，保证答案的十进制位数不超过200位。
Solution
把题目中树的边看成点，点看成边，题目就转化为求深度为d的n叉树的个数（根节点深度为1）。
直觉告诉我们，深度在d以内的树的个数 比 深度为d的树的个数 好求，所以，设f[d]=深度在d以内的树的个数。
然后 深度为d的树的个数 = 深度在d以内的树的个数 - 深度在d-1以内的树的个数 = f[d] - f[d-1]。
然而小C一开始还是没有头绪，开始DP打表观察规律。
然后就观察出了递推式：f[x] = f[x-1]^n+1 (1<=x<=d , f[0] = 1)。
仔细想想为什么呢？我们用n棵深度在x-1以内的树作为儿子，再加上根节点就变成深度在x以内的树啦！
最后+1是因为还要加上深度为0的空树。
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MOD 10000
#define MS 400
#define MN 20
using namespace std;
struct hp
{
int len,a[MS];
void add() {++a[];}
friend hp operator-(const hp& A,const hp& B)
{
hp C=A;
register int i;
for (i=;i<=B.len;++i)
{
C.a[i]-=B.a[i];
if (C.a[i]<) --C.a[i+],C.a[i]+=MOD;
}
while (!C.a[C.len]) --C.len;
return C;
}
friend hp operator*(const hp& A,const hp& B)
{
hp C; C.len=A.len+B.len+;
register int i,j;
memset(C.a,,sizeof(C.a));
for (i=;i<=A.len;++i)
for (j=;j<=B.len;++j)
C.a[i+j-]+=A.a[i]*B.a[j];
for (i=;i<C.len;++i)
C.a[i+]+=C.a[i]/MOD,C.a[i]%=MOD;
while (!C.a[C.len]) --C.len;
return C;
}
}f[MN],ans;
int m,n; inline int read()
{
int n=,f=; char c=getchar();
while (c<'' || c>'') {if(c=='-')f=-; c=getchar();}
while (c>='' && c<='') {n=n*+c-''; c=getchar();}
return n*f;
} hp mi(hp x,int y)
{
hp z;
memset(z.a,,sizeof(z.a)); z.len=z.a[]=;
for (;y;y>>=,x=x*x) if (y&) z=z*x;
return z;
} int main()
{
register int i;
m=read(); n=read();
if (n<=) return *printf("");
f[].len=; f[].a[]=;
for (i=;i<=n;++i) f[i]=mi(f[i-],m),f[i].add();
ans=f[n]-f[n-];
printf("%d",ans.a[ans.len]);
for (i=ans.len-;i;--i) printf("%04d",ans.a[i]);
}
Last Word
果然还是观察规律好用。
一道还算不错的题因为掺了高精度而风评被害。