A22706.神奇口袋

省选/NOI-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

Pòlya 获得了一个奇妙的口袋,上面写着人类难以理解的符号。Pòlya 看得入了迷,冥思苦想,发现了一个神奇的模型(被后人称为 Pòlya 模型)。为了生动地讲授这个神奇的模型,他带着学生们做了一个虚拟游戏:游戏开始时,袋中装入 a1a_1 个颜色为 11 的球,a2a_2 个颜色为 22 的球,……,ata_t 个颜色为 tt 的球,其中 aiZ+a_i \in \mathbb Z^+1it1 \le i \le t)。

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

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

cic_i 表示第 ii 次抽出的小球的颜色(1Cit1 \le C_i \le t),一个游戏过程将会产生一个颜色序列(c1,c2,,cn,c_1, c_2, \ldots, c_n, \ldots)。Pòlya 把游戏开始时 tt 种颜色的小球每一种的个数 a1,a2,,ata_1, a_2, \ldots, a_t 告诉了所有学生。然后他问学生:一次游戏过程产生的颜色序列满足下列条件的概率有多大?

cx1=y1,cx2=y2,,cxn=ync_{x_1}=y_1, c_{x_2}=y_2, \ldots, c_{x_n}=y_n

其中 0<x1<x2<<xn0 < x_1 < x_2 < \cdots < x_n1yit1 \le y_i \le t。换句话说,已知 (t,n,d,a1,a2,,at,x1,y1,x2,y2,,xn,yn)(t, n, d, a_1, a_2, \ldots, a_t, x_1, y_1, x_2, y_2, \ldots, x_n, y_n),你要回答有多大的可能性会发生下面的事件:“对所有 kk1kn1 \le k \le n),第 xkx_k 次抽出的球的颜色为 yky_k”。

输入格式

第一行有三个正整数 t,n,dt, n, d

第二行有 tt 个正整数 a1,a2,,ata_1, a_2, \ldots, a_t,表示游戏开始时口袋里 tt 种颜色的球,每种球的个数。

以下 nn 行,每行有两个正整数 xi,yix_i, y_i,表示第 xix_i 次抽出颜色为的 yiy_i 球。

输出格式

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

输入输出样例

  • 输入#1

    2 3 1
    1 1
    1 1
    2 2
    3 1
    

    输出#1

    1/12
    
  • 输入#2

    3 1 2
    1 1 1
    5 1
    

    输出#2

    1/3
    

说明/提示

【样例解释 #1】

初始时,两种颜色球数分别为 (1,1)(1, 1),取出色号为 11 的球的概率为 1/21/2;第二次取球之前,两种颜色球数分别为 (2,1)(2, 1),取出色号为 22 的球的概率为 1/31/3;第三次取球之前,两种颜色球数分别为 (2,2)(2, 2),取出色号为 11 的球的概率为 1/21/2,所以三次取球的总概率为 1/121/12

【数据规模和约定】

对于 100%100 \% 的数据,1t,n10001 \le t, n \le 10001ak,d101 \le a_k, d \le 101x1<x2<<xn100001 \le x_1 < x_2 < \cdots < x_n \le 100001ykt1 \le y_k \le t

首页