BZOJ1005 [HNOI2008]明明的烦恼

2014.12.16 16:30 Tue| 6 visits oi_2015| 2015_刷题日常| Text

热烈庆祝自己第一次写的稍稍麻烦一点点的Python!!

Solution

树的Prufer序列和树是一一对应的。因此可以运用排列组合的只是一通乱搞+化简即可。需要用到高精度。由于化简后会出现高精度除法,而组合数中结果必定是整数,因此需要把阶乘分解素因数之后用加减代替乘除……各种麻烦啊……据说还有各种特判。

既然是高精度,怎能少了Python?没加一个特判貌似仍然AC了此题。

Python大法好!!!

Code

def f(n):
    c = 1
    for i in range(1, n+1):
        c *= i
    return c

a={}
n=int(input(""))
ans=f(n-2)
tot=cnt=0
for i in range(1, n+1):
    a[i]=int(input(""))
    if(a[i] > 0):
        ans /= f(a[i]-1)
        tot += a[i]-1
    else:
        cnt += 1
ans *= cnt**(n-2-tot)
ans /= f(n-2-tot)
print(int(ans))