a180: NOI2006 Day2.3.神奇口袋
Tags :
Accepted rate : 9人/11人 ( 82% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 03:15

Content
Pòlya 获得了一个奇妙的口袋,上面写着人类难以理解的符号。Pòlya 看得入了迷,冥思苦想,发现了一个神奇的模型(被后人称为Pòlya 模型)。为了生动

地讲授这个神奇的模型,他带着学生们做了一个虚拟游戏:

 游戏开始时,袋中装入a1 个颜色为1 的球,a2 个颜色为2 的球,at

个颜色为t 的球,其中aiZ+ (1it)

 

游戏开始后,每次严格进行如下的操作:

 从袋中随机的抽出一个小球(袋中所有小球被抽中的概率相等),Pòlya 独自观察这个小球的颜色后将其放回,然后再把d 个与其颜色相同

的小球放到口袋中。

 ci表示第i次抽出的小球的颜色(1cit) ,一个游戏过程将会产生一个颜

色序列(c1,c2,…,cn,…)

 Pòlya 把游戏开始时t 种颜色的小球每一种的个数a1,a2,…,at 告诉了所有学生。然后他问学生:一次游戏过程产生的颜色序列满足下列条件的概率有多大? Cx1=y1, Cx2=y2,……, Cxi=yi,……, Cxn=yn 其中0<x1<x2<…<xn 1≤yit 。换句话说, 已知(t , n , d , a1,a2,…,at ,x1,y1,x2,y2,...,xn,yn),你要回答有多大的可能性会发生下面的事件:对所有k,1≤kn,第xk 次抽出的球的颜色为yk

 

Input

第一行有三个正整数t,n,d;第二行有t 个正整数a1,a2,…,at,表示游戏开
始时口袋里t 种颜色的球,每种球的个数。


以下n 行,每行有两个正整数xi,yi,表示第xi 次抽出颜色为的yi 球。

Output

要求用分数形式输出(显然此概率为有理数)。输出文件包含一行,格式为:
分子/分母。同时要求输出最简形式(分子分母互质)。特别的,概率为0 应输出
0/1,概率为1 应输出1/1。

Sample Input
【样例1】
2 3 1
1 1
1 1
2 2
3 1
【样例2】
3 1 2
1 1 1
5 1
Sample Output
【样例1】
1/12
【样例2】
1/3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
Hint :

【样例1 说明】
初始时,两种颜色球数分别为(1, 1),取出色号为1 的球的概率为1/2;第二
次取球之前,两种颜色球数分别为(2, 1),取出色号为2 的球的概率为1/3;第三
次取球之前,两种颜色球数分别为(2, 2),取出色号为1 的球的概率为1/2,所以
三次取球的总概率为1/12。


【数据规模和约定】
1≤t,n≤1000, 1≤ak ,d≤10, 1≤x1

//在比赛时有6个测资点有误,这里更正 by liouzhou_101。

Tags:
出處:
NOI2006Day2第三题 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」