Bài tập | NEU OJ

Cho hai biến ngẫu nhiên rời rạc độc lập $X \in \{0,1,\dots,m\}$ và $Y \in \{0,1,\dots,n\}$ . Phân phối của $X$ được cho bởi các số đếm nguyên không âm $c_0, c_1, \dots, c_m$ với $P(X=i) = c_i / D_1$ trong đó $D_1 = \sum_i c_i$ ; tương tự $P(Y=j) = d_j / D_2$ với $D_2 = \sum_j d_j$ (đảm bảo bởi đề).

Đặt $Z = X + Y$ . Vì $X, Y$ độc lập, $P(Z=k) = \sum_{i+j=k} P(X=i)P(Y=j)$ (tích chập).

Cho $q$ truy vấn giá trị nguyên $k$ , với mỗi truy vấn hãy in ra $P(Z=k)$ dưới dạng phân số tối giản p/q. Quy ước: nếu $P(Z=k)=0$ (kể cả khi $k \notin [0, m+n]$ ), in ra 0/1.

Ví dụ: $X$ đều trên $\{0,1\}$ ( $c=(1,1)$ , $D_1=2$ ), $Y$ đều trên $\{0,1,2\}$ ( $d=(1,1,1)$ , $D_2=3$ ). Khi đó $Z \in \{0,1,2,3\}$ với xác suất $1/6, 1/3, 1/3, 1/6$ .

Input:

Output:

0/1
1/6
1/3
1/3
1/6
0/1

Định dạng đầu vào:
Dòng 1: hai số nguyên $m$ và $D_1$ . Dòng 2: $m+1$ số nguyên không âm $c_0, \dots, c_m$ (tổng bằng $D_1$ ). Dòng 3: hai số nguyên $n$ và $D_2$ . Dòng 4: $n+1$ số nguyên không âm $d_0, \dots, d_n$ (tổng bằng $D_2$ ). Dòng 5: số nguyên $q$ ( $q \ge 0$ ). Trong $q$ dòng tiếp theo, mỗi dòng chứa một số nguyên $k$ (có thể âm, có thể vượt quá $m+n$ ).
Định dạng đầu ra:
In ra $q$ dòng, dòng thứ $j$ là $P(Z=k_j)$ dưới dạng phân số tối giản p/q (mẫu số dương). Nếu xác suất bằng 0, in 0/1.

solution

Đề bài: [Xác suất - Thống kê] Tích chập của hai biến ngẫu nhiên độc lập