Editorial for Matrix Exponentiation - Count path

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: 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.

Comments

Please read the guidelines before commenting.

There are no comments at the moment.