/ Vijos / 题库 /

神奇口袋

神奇口袋

描述

Pòlya 获得了一个奇妙的口袋,上面写着人类难以理解的符号。Pòlya 看得入了迷,冥思苦想,发现了一个神奇的模型(被后人称为Pòlya 模型)。为了生动地讲授这个神奇的模型,他带着学生们做了一个虚拟游戏:

游戏开始时,袋中装入\(a_1\)个颜色为1 的球,\(a_2\)个颜色为2的球,…,\(a_t\)个颜色为t的球,其中每一个\(a_i\)都是正整数。

游戏开始后,每次严格进行如下的操作:从袋中随机的抽出一个小球(袋中所有小球被抽中的概率相等),Pòlya 独自观察这个小球的颜色后将其放回,然后再把d个与其颜色相同的小球放到口袋中。

设\(c_i\)表示第i次抽出的小球的颜色\(1\le c_i \le t\),一个游戏过程将会产生一个颜色序列\((c_1,c_2,\cdots,c_n,\cdots)\)。

Pòlya 把游戏开始时t 种颜色的小球每一种的个数\(a_1,a_2,\cdots,a_t\)告诉了所有学生。然后他问学生:一次游戏过程产生的颜色序列满足下列条件的概率有多大?

\(c_{x_1} = y_1,~c_{x_2} = y_2,~\cdots,~c_{x_i} = y_i,~\cdots,~c_{x_n} = y_n.\)

其中\(0<x_1<x_2<\cdots <x_n\),\(1\le y_i\le t\)。换句话说, 已知\((t,n,d,a_1,a_2,\cdots ,a_t,x_1,y_1,x_2,y_2,\cdots ,x_n,y_n)\),你要回答有多大的可能性会发生下面的事件:“对所有\(k,~1\le k\le n\),第\(x_k\)次抽出的球的颜色为\(y_k\)”。

格式

输入格式

第一行有三个正整数t,n,d(\(1\le t,n\le 1000\));第二行有t 个正整数\(a_1,a_2,\cdots,a_t~(1\le a_k,~d\le 10)\),表示游戏开始时口袋里t种颜色的球,每种球的个数。
以下n 行,每行有两个正整数\(x_i,y_i\),(\(1\le x_1\le x_2<\cdots <x_n\le 10000\),\(1\le y_k\le t\)),表示第\(x_i\)次抽出颜色为的\(y_i\)球。

输出格式

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

样例1

样例输入1

2 3 1
1 1
1 1
2 2
3 1

样例输出1

1/12

样例2

样例输入2

3 1 2
1 1 1
5 1

样例输出2

1/3

限制

每个测试点1s。

提示

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

来源

NOI 2006 Day 2

信息

ID
1833
难度
3
分类
(无)
标签
递交数
49
已通过
27
通过率
55%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库