Pòlya's Urn Model - Forced Draw Sequence Probability

Pòlya discovered a magical urn with mysterious symbols. Initially the urn contains \(a_1\) balls of color 1, \(a_2\) balls of color 2, …, \(a_t\) balls of color \(t\) (with \(a_i \in \mathbb{Z}^+\)). Then a virtual game is played as follows: at every step, a ball is drawn uniformly at random. Pòlya looks at its color, returns it to the urn, and adds \(d\) additional balls of the same color.

Let \(c_i\) be the color drawn at step \(i\). Given indices \(0 < x_1 < x_2 < \cdots < x_n\) and colors \(y_1,y_2,\ldots,y_n\) (with \(1 \le y_i \le t\)), you are to compute the probability that in one game process the forced events

[ { c_{x_1} = y_1,; c_{x_2} = y_2,; \ldots,; c_{x_n} = y_n } ]

occur. By the exchangeability of the Polya urn process, the probability is given by the Dirichlet-multinomial formula:

[ P = \frac{\Gamma\Bigl(\sum_{j=1}^t\frac{a_j}{d}\Bigr)}{\Gamma\Bigl(\sum_{j=1}^t\frac{a_j}{d}+n\Bigr)}\prod_{j=1}^{t}\frac{\Gamma\Bigl(\frac{a_j}{d}+k_j\Bigr)}{\Gamma\Bigl(\frac{a_j}{d}\Bigr)}, ]

where \(k_j\) is the number of forced draws that produce color \(j\). Note that the positions \(x_1,x_2,\ldots,x_n\) do not affect the answer (other than determining \(n\)) due to the process's exchangeability.

inputFormat

The input consists of three parts:

1. The first line contains three integers \(t\), \(n\), and \(d\) representing the number of colors, the number of forced draws, and the number of balls to add after each draw.
2. The second line contains \(t\) positive integers: \(a_1, a_2, \ldots, a_t\) (the starting ball counts for each color).
3. The third line contains \(2n\) integers: \(x_1\; y_1\; x_2\; y_2\; \ldots\; x_n\; y_n\), where each \(x_i\) (with \(x_1 < x_2 < \cdots < x_n\)) specifies a draw position and \(y_i\) (with \(1 \le y_i \le t\)) is the required color at that position.

outputFormat

Output a single real number representing the probability that the event \(c_{x_1}=y_1, c_{x_2}=y_2, \ldots, c_{x_n}=y_n\) occurs. The answer is accepted if its absolute or relative error is at most \(10^{-6}\).

sample

2 1 1
1 1
1 1

0.5