AC. 梦想

frank_c1

[BZOJ 1089] 严格n元树

发布于2016年04月19日 | 暂无评论 | 453阅读 | 递推

题目描述

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

给出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上似乎没写,还以为自己高精度姿势不对呢……