BZOJ1416&BZOJ1498 [NOI2006]神奇的口袋

2014.12.23 10:54 Tue| 1 visits oi_2015| 2015_刷题日常| Text

额,就为了这个双倍经验,一定要把这道题水过!!

努力了两天,终于如愿以偿。当然,和往常一样,这么赤果果的高精度,一定要用Python!!

常说的多一门语言多一条路果然说的不错。经历这一道题的历练,我对于Python中字典理解应该上了一个层次了呢……【之前我还一直当它是一个普通的数组】

Solution

其实这可以说是一道数学题。

有一点奇怪的性质:最终的答案与进行取球的顺序无关(看这简洁生动的代码就可以理解这句话了)。

感性的想一下,好像也有它的道理……

证明如下:

对于两个相邻的操作x[i]=x[j]-1

  • y[i]=y[j]
    显然进行将这两个操作进行交换后答案不变;

  • y[i]≠y[j]
    不妨设i=j-1。
    第x[i]次取出y[i]的概率 p1=a[y[i]]/s
    第x[j]次取出y[j]的概率 p2=a[y[j]]/(s+d)
    第x[i]次取出y[j]的概率 p3=a[y[j]]/s
    第x[j]次取出y[i]的概率 p4=a[y[i]]/(s+d)
    由于p1*p2=p3*p4,交换后答案不变。

综上,最终的答案与进行取球的顺序无关。

最后用Python写一写就好啦~双倍经验哦!

Code

def gcd(a,b):
    if(b == 0): return a
    return gcd(b, a%b)

t,n,d = raw_input().split()
a = map(int, raw_input().split())

s = 0
for i in range(0, int(t)):
    s += int(a[i])

x = {}
for i in range(1, int(n)+1):
    r = raw_input().split()
    x[i] = int(r[1])-1

up = down = 1
for i in range(1, int(n)+1):
    up *= a[x[i]]
    down *= s
    s += int(d)
    a[x[i]] += int(d)
g = gcd(up,down)
print("%d/%d" %(up/g, down/g))