Editorial for Matrix Exponentiation - Count path
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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:
~\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.
Comments