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

题目链接

https://www.luogu.org/problem/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])

发表回复

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据