Lũy Thừa Ma Trận Xác Suất
Points
85
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một chuỗi Markov gồm $N$ trạng thái đánh số từ $1$ đến $N$. Mỗi trạng thái $i$ có giá trị thưởng $val[i]$.
Tại mỗi bước, nếu đang ở trạng thái $i$, hệ thống sẽ chuyển sang trạng thái $j$ với xác suất $p_{i,j} = \frac{w_{i,j}}{\sum_{k=1}^N w_{i,k}}$ (trong đó $w_{i,j}$ là trọng số không âm và $\sum_{k=1}^N w_{i,k} > 0$).
Người chơi bắt đầu ở trạng thái $1$ (tại thời điểm $0$, nhận thưởng $val[1]$) và thực hiện đúng $T$ bước chuyển trạng thái (tại các thời điểm $1, 2, \dots, T$, mỗi lần tới trạng thái $u$ nhận thêm $val[u]$).
Hãy tính kỳ vọng tổng số điểm thưởng nhận được sau $T$ bước (bao gồm cả thời điểm $0$), theo modulo $10^9 + 7$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, T$ ($1 \le N \le 50$, $0 \le T \le 10^{18}$).
- Dòng thứ hai chứa $N$ số nguyên $val[1], \dots, val[N]$ ($0 \le val[i] \le 10^9$).
- $N$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên $w_{i,1}, \dots, w_{i,N}$ ($0 \le w_{i,j} \le 10^6$, tổng mỗi hàng dương).
Dữ liệu ra
- In ra một số nguyên duy nhất là kỳ vọng tổng điểm thưởng theo modulo $10^9 + 7$.
Ví dụ
Input
2 2
10 20
1 1
0 1
Output
500000046
Giải thích
- Thời điểm 0: ở 1, thưởng $10$.
- Thời điểm 1: ở 1 (xác suất $1/2$) hoặc 2 (xác suất $1/2$), kỳ vọng thưởng $15$.
- Thời điểm 2: ở 1 (xác suất $1/4$) hoặc 2 (xác suất $3/4$), kỳ vọng thưởng $\frac{1}{4}(10) + \frac{3}{4}(20) = \frac{35}{2}$. Tổng kỳ vọng: $10 + 15 + \frac{35}{2} = \frac{85}{2} \equiv 500000046 \pmod{10^9+7}$.
Giới hạn
- $1 \le N \le 50$
- $0 \le T \le 10^{18}$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion