Hướng dẫn giải của Matrix Exponentiation - Count path

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: dquynh_2811

Kí hiệu ~adj(u)~ là tập hợp các đình có đường đi trực tiếp tới ~u~.

Hãy đi từ ý tưởng đơn giản nhất, gọi ~dp[u][i]~ là số đường đi từ bất cứ đỉnh nào đến đỉnh ~u~ trong ~i~ bước. Dễ thấy, ta có công thức chuyển trạng thái là: ~dp[u][i] = \sum_{v \in adj(u)}dp[v][i - 1]~.

Thuật toán này có độ phức tạp ~O(K\times M)~, không thể xử lý được với giới hạn ~10^9~ của ~k~.

Để cải tiến, ta sử dụng thuật toán Nhân ma trận.

Với ma trận ~A~ là ma trận kề của đồ thị, gọi ~dp_i~ là vector mà phần tử thứ ~u~ là số đường đi có độ dài ~i~ và kết thúc tại ~u~ (nói cách khác ~dp_i[u] = dp[u][i]~ theo công thức QHĐ bên trên). Từ ý tưởng QHĐ, ta có: ~dp_{i + 1} = A \times dp_i~, vậy ta cũng có được:

~\begin{array}{lcl} dp_n &=& A \times dp_{n - 1} \\ &=& A \times A \times dp_{n - 2} \\ &=& A \times A \times A \times dp_{n - 3}\\ & = &... = A^n \times dp_0 \end{array}~ Với ~dp_0~ là ma trận: ~\begin{bmatrix} 1 \\ 1 \\ 1 \\ ... \\ 1 \end{bmatrix}~

~\rightarrow~ Ta có ý tưởng lũy thừa ma trận bằng ~\log\ k~ lần nhân ma trận.

Độ phức tạp: ~O(N^3 \times log\ k)~

Code tham khảo

Tham khảo code của Errichto tại đây.

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.