Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Xác suất - Thống kê] Phân phối chính xác của tổng mẫu rời rạc

    Định lý giới hạn trung tâm cho ta xấp xỉ phân phối của tổng mẫu khi nnn lớn, nhưng với nnn nhỏ ta có thể tính chính xác phân phối này bằng phép chập (convolution), không cần xấp xỉ.

    Cho một biến ngẫu nhiên rời rạc XXX nhận các giá trị nguyên với xác suất tương ứng cho dưới dạng phân số (tổng các xác suất đúng bằng 1). Lấy mẫu ngẫu nhiên độc lập nnn lần X1,X2,…,XnX_1, X_2, \dots, X_nX1​,X2​,…,Xn​ (mỗi XiX_iXi​ có cùng phân phối như XXX, độc lập với nhau). Hãy tính chính xác (bằng số học phân số, không làm tròn) xác suất:

    P(X1+X2+⋯+Xn=k)P(X_1 + X_2 + \dots + X_n = k)P(X1​+X2​+⋯+Xn​=k)

    với kkk cho trước.

    Ví dụ

    Input:

    2
0 1/2
1 1/2
3 2

    (nghĩa là XXX nhận giá trị 000 với xác suất 1/21/21/2, giá trị 111 với xác suất 1/21/21/2; lấy mẫu n=3n=3n=3 lần, tính P(tổng=2)P(\text{tổng}=2)P(tổng=2))

    Output:

    3/8
    • Định dạng đầu vào:

      Dòng 1: số nguyên mmm (1≤m≤61 \le m \le 61≤m≤6) — số giá trị có thể của XXX. mmm dòng tiếp theo, mỗi dòng dạng v p trong đó vvv là số nguyên (−20≤v≤20-20 \le v \le 20−20≤v≤20, các vvv đôi một khác nhau) và ppp là xác suất viết dưới dạng phân số a/b (a, b là số nguyên dương). Tổng các ppp trên toàn bộ mmm dòng đảm bảo đúng bằng 1. Dòng cuối: hai số nguyên n kn\ kn k cách nhau bởi khoảng trắng, trong đó nnn là số lần lấy mẫu (1≤n≤81 \le n \le 81≤n≤8) và kkk là giá trị tổng cần tính xác suất (−160≤k≤160-160 \le k \le 160−160≤k≤160).

    • Định dạng đầu ra:

      In ra xác suất P(X1+⋯+Xn=k)P(X_1+\dots+X_n=k)P(X1​+⋯+Xn​=k) dưới dạng phân số tối giản a/b (nếu kết quả bằng 0, in 0/1; nếu bằng 1, in 1/1).

    Ví dụ:

    Đầu vào:

    3
-1 1/6
0 2/6
2 3/6
8 5

    Đầu ra:

    385/3888

    Đầu vào:

    2
0 1/2
1 1/2
3 2

    Đầu ra:

    3/8

    Đang tải editor...