题目描述

如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d
（根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为２的严格２元树有三个，如下图：

给出n, d，编程数出深度为d的n元树数目。

输入格式

仅包含两个整数$n, d( 0 \lt n \le 32,0 \le d \le 16)$

输出格式

仅包含一个数，即深度为d的n元树的数目。

题目解析

一道小清新的计数题~~

设$f(i)$为深度为$i$的严格$n$元树数目。方便起见，定义$g(i) = \sum_{j=0}^{i-1} {f(i)}$，即深度$\lt i$的严格$n$元树数目。

现在我们考虑一棵深度为$i(i \ge 1)$的严格$n$元树是怎样组成的。

首先，根节点必有恰好$n$个儿子。每个儿子所在的子树一定是一棵深度$\le i-1$的严格$n$元树，按这个思路，转移就是$f(i) = g(i) ^ n$？显然我们计算了一些不合法的情况，若每棵子树深度均$\lt i-1$，这棵树深度就无法达到$i$。稍微改变一下思路，考虑枚举深度恰好为$i-1$的子树，则有

$$f(i) = \sum_{j=1}^{n} {{n \choose j} f(i-1) ^ j g(i-1) ^ {n-j}}$$

这样我们就保证至少有一棵子树的深度达到$i-1$，其他子树$\le i-1$，满足题意。

令人比较不爽的是需要用高精度计算。答案可能非常大，原题保证答案不超过200位10进制整数，然而BZOJ上似乎没写，还以为自己高精度姿势不对呢……