solution

Bộ sinh số giả ngẫu nhiên (để kết quả tái lập được, không dùng random thật): Cho số nguyên seed $\ge 0$. Đặt $s_0=\text{seed}$. Với $i=1,2,3,\dots$: $s_i = (1103515245 \cdot s_{i-1} + 12345) \bmod 2^{31}.$ Số ngẫu nhiên thứ $i$ là $u_i = s_i / 2^{31} \in [0,1)$. Dãy $u_1,u_2,u_3,\dots$ được lấy theo ĐÚNG thứ tự này, dùng tuần tự trong suốt quá trình mô phỏng.

Bài toán: Cho một xích Markov rời rạc gồm $k$ trạng thái đánh số $0,1,\dots,k-1$ ($2\le k\le 5$). Ma trận chuyển được cho dưới dạng phân số với mẫu số chung $Q$: dòng thứ $i$ gồm $k$ số nguyên không âm $p_{i,0},\dots,p_{i,k-1}$ với $\sum_j p_{i,j} = Q$; xác suất chuyển từ trạng thái $i$ sang $j$ là $p_{i,j}/Q$.

Xét ngưỡng tích lũy của dòng $i$: $c_{i,0} = p_{i,0}/Q$, $c_{i,j} = c_{i,j-1} + p_{i,j}/Q$ với $j\ge 1$. Trạng thái bắt đầu luôn là $0$.

Mô phỏng $M$ chuỗi độc lập, mỗi chuỗi $T$ bước; số ngẫu nhiên lấy TUẦN TỰ toàn cục: chuỗi $1$ dùng $T$ số đầu tiên (mỗi bước 1 số), rồi đến chuỗi $2$, v.v. Tại một bước, đang ở trạng thái $i$, lấy số ngẫu nhiên kế tiếp $u$; trạng thái kế tiếp là chỉ số $j$ NHỎ NHẤT sao cho $u < c_{i,j}$ (nếu do sai số không tìm được $j$ nào, quy ước chọn $j=k-1$).

Sau khi mô phỏng xong (tổng cộng $M\times T$ bước, TRẠNG THÁI XUẤT PHÁT KHÔNG được tính), đếm số bước rơi vào mỗi trạng thái và in ra $k$ tỉ lệ (đếm/$(M\times T)$), làm tròn 6 chữ số thập phân, theo đúng thứ tự trạng thái $0,1,\dots,k-1$, cách nhau khoảng trắng (quy ước toàn bộ $=0$ nếu $M\times T=0$).

Ví dụ: $k=2, Q=2, M=2, T=3, \text{seed}=1$, ma trận $\begin{pmatrix}1&1\\1&1\end{pmatrix}$ (mỗi dòng chia đều $Q=2$) → 0.500000 0.500000.