[洛谷 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])