Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

05/10
09:03
一般动规与递推 高精度

[bzoj 1089] SCOI2003 严格n元树

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

仅包含两个整数n, d( 0   <   n   <   =   32,   0  < =   d  < = 16)

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

【样例输入1】
2 2

【样例输入2】
2 3

【样例输入3】
3 5

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

【样例输出1】
3

【样例输出2】
21

【样例输出2】
58871587162270592645034001

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

高精度dp

我们设f[i]表示dep<=i的严格n元树,那么答案就是f[d]-f[d-1]

对于一个dep<=i严格n元树,我们可以这样考虑:新加进一个根节点,他的每一个叶节点都是一棵dep<=i-1的严格n元树,所以每个叶节点都有f[i-1]种选择的方式,然后一共有n个叶节点,再加上一个叶节点都没有(深度为0)的情况,所以f[i]=f[i-1]^n+1,用高精度递推一下就行了

ps:话说那数据范围是虚的吧,最大数据根本过不去QAQ

pascal:

c++:

 

[bzoj 1089] SCOI2003 严格n元树