Bài tập | NEU OJ

Cho hai biến ngẫu nhiên rời rạc độc lập $X$ và $Y$ , mỗi biến cho bởi bảng phân phối xác suất dạng phân số. Tính phân phối xác suất của $Z = X + Y$ , tức $P(Z=z) = \sum_{x+y=z} P(X=x)P(Y=y)$ .

Ví dụ: $X, Y$ đều tung một xúc xắc cân đối 6 mặt ( $P=1/6$ cho mỗi giá trị $1,\dots,6$ ). Khi đó $P(Z=2)=1/36$ , $P(Z=7)=1/6$ , v.v. (đây chính là bài toán tổng hai xúc xắc cổ điển).

Định dạng đầu vào:
Dòng 1: $n$ — số giá trị của $X$ ( $1 \le n \le 30$ ). $n$ dòng tiếp theo: $x_i\ a_i\ b_i$ nghĩa là $P(X=x_i) = a_i/b_i$ ( $x_i$ đôi một phân biệt, $1\le b_i \le 10^6$ , $0 \le a_i \le b_i$ ). Dòng tiếp theo: $m$ — số giá trị của $Y$ ( $1 \le m \le 30$ ). $m$ dòng tiếp theo: $y_j\ c_j\ d_j$ nghĩa là $P(Y=y_j) = c_j/d_j$ ( $y_j$ đôi một phân biệt). Đảm bảo $\sum_i a_i/b_i = 1$ và $\sum_j c_j/d_j = 1$ chính xác.
Định dạng đầu ra:
In các dòng, mỗi dòng có dạng z p/q, theo thứ tự $z$ tăng dần, trong đó $P(Z=z) = p/q$ đã được rút gọn tối giản ( $q > 0$ ). Chỉ in những giá trị $z$ có xác suất khác 0 (không in các $z$ với $P(Z=z)=0$ ).

solution

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