Nếu bạn dùng cách làm của bài Count Paths - Tính lũy thừa ma trận cho mỗi truy vấn, độ phức tạp sẽ là ~O(Q \cdot N^3 \cdot log \ k)~, quá chậm để qua được bài này.

Vậy, ta thử suy nghĩ tới thuật toán cải tiến: Giảm độ phức tạp cho mỗi lần trả lời truy vấn bằng cách chuẩn bị trước trạng thái ma trận khi độ dài của đường đi có dạng lũy thừa của ~2~ : ~2^i~ ~(0 \le i < 30)~.

Gọi ~cnt_{ a,\ b,\ c}~ là số đường đi xuất phát từ ~a~, kết thúc tại ~b~ và đi qua ~2^c~ cạnh. Bây giờ với mỗi truy vấn xuất phát từ ~s~ và kết thúc tại tại ~t~ cần đi qua ~k~ cạnh, ta phân tích ~k~ thành tổng các lũy thừa cơ số ~2~ và đáp án của ta là: ~cnt_{s,\ u_1,\ k_1} \times cnt_{u_1,\ u_2,\ k_2} \times ... \times cnt_{u_{x-1},\ t,\ k_x}~. Trong đó:

• ~1 \le u_1,\ u_2,\ …,\ u_{x-1} \le n,\ u_0 = s~.
• ~0 \le k_1,\ k_2,\ ...,\ k_x \le log \ k~.
• ~s,\ u_1,\ u_2,\ ...,\ u_{x-1},\ t~ là các đỉnh thuộc cùng một đường đi từ ~s~ tới ~t~.
• ~2^{k_1} + 2^{k_2} + … + 2^{k_x} = k~.

Bằng ma trận đã được chuẩn bị trước, ta có thể tính ngay được số đường đi xuất phát từ một đỉnh ~u~ đi qua ~2^i~ cạnh và kết thúc tại đỉnh ~v~. Có thể tìm nhanh ~k_1,\ k_2,\ ...,\ k_x~ bằng cách xét các bit ~1~ trong biểu diễn nhị phân của ~k~.

Ta xét lần lượt các bit ~1~ của ~k~, lưu lại mảng ~f~ với ý nghĩa ~f[i][w]~ là số đường đi xuất phát từ ~s~ đi qua số cạnh bằng tổng lũy thừa cơ số ~2~ các vị trí bit ~1~ trong các bit từ ~0~ đến ~i~ và kết thúc tại ~w~, ta có công thức chuyển trạng thái như sau:

• Nếu bit ~i~ hiện tại là ~0~, ~f[i][w] = f[i-1][w]~.
• Ngược lại ~f[i][w] = \sum {f[i-1][q] * cnt_{q,\ w,\ i}}~.

Có thể tối ưu mảng ~f~ hơn bằng cách đưa về ~2~ mảng ~dp[q]~ thay cho ~f[i - 1][q]~ và ~new\_dp[w]~ thay cho ~f[i][w]~, gán giá trị cho mảng ~dp~ bằng mảng ~new\_dp~ trước mỗi lần duyệt sang bit mới. Đáp án cần tìm chính là ~dp[t]~.

Độ phức tạp: ~O( N^3 \cdot log \ k + Q \cdot N^2 \cdot log \ k)~

Code tham khảo

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