[BZOJ1089][SCOI2003]严格n元树(递推+高精度)

时间:2023-02-04 08:56:15

题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1089

分析:

第一感觉可以用一个通式求出来,但是考虑一下很麻烦,不好搞的。很容易发现最底层必有一个是满高度的,其他的任意。

所以直接的递推也不好想。

(以下所述都是n元树)

于是可以令f[d]为深度<=d的树的个数,那么深度为d的就是f[d]-f[d-1]

对于深度<=d的又该怎么处理呢?

考虑第一层的n个点(根为0层),每个点都要底下连子树,深度为0~i-1,方案数即f[d-1],而且这n个点互不影响

所以f[d]=f[d-1]^n+1(注意这个要加1,即只有一个根节点的情况)

然后注意高精度就可以了。