BZOJ1089 [SCOI2003]严格n元树

2014.12.31 10:45 Wed| 2 visits oi_2015| 2015_刷题日常| Text

Solution

數學啊!!數學!!

可能很显然?记深度不大于d的严格n元树数目为 $f_d$ ,则 $f_d = f_{d-1} ^ n +1$ 。

即,一个深度深度不大于d的严格n元树数目可看做由一个根节点和其上连接的深度不大于d-1的严格n元树构成,共有方案 $f_{d-1} ^ n$ 种。另外,单独一个根节点也符合题意,即得到上述递推式。

高精度啊!!高精度!!

Python?→_→

Code

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