[洛谷 4295][SCOI2003]严格N元树

题目链接

https://www.luogu.org/problemnew/show/P4295

题解

用\(f_i\)表示深度不超过\(i\)的严格\(n\)元树的数量。

那么可以这样递推:\(f_i=f_{i-1}^n+1\)。

边界条件为\(f_0=1\)(就是单独的根节点嘛)。

我们要求的是深度恰好为\(n\)的树,那么答案便是\(f_n-f_{n-1}\)。

(高精度太毒瘤了,所以我用python)

s=input().split()
n=int(s[0])
d=int(s[1])
f=[1]
if(d==0):
    print(1)
else:
    for i in range(1,d+1):
        f.append(f[i-1]**n+1)
    print(f[d]-f[d-1])

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注