Hướng dẫn giải: Nhảy K Bước

Phân tích bài toán

Bài toán yêu cầu thực hiện mô phỏng đi đúng \(K\) bước từ đỉnh \(U\) trên một đồ thị hàm số (functional graph), với mỗi đỉnh \(i\) có đỉnh đi tới kế tiếp là \(next[i]\). Với \(K\) lên tới \(10^{18}\), mô phỏng tuyến tính từng bước một sẽ bị TLE. Do đó ta sử dụng kỹ thuật Nhảy nhị phân (Binary Lifting):

• Định nghĩa mảng hai chiều up[i][j] là đỉnh đạt được từ \(i\) sau khi đi \(2^j\) bước.
• Cơ sở: up[i][0] = next[i].
• Công thức quy hoạch động: up[i][j] = up[up[i][j-1]][j-1] (nhảy \(2^j\) bước = nhảy \(2^{j-1}\) bước 2 lần).
• Để trả lời truy vấn nhảy \(K\) bước, ta biểu diễn \(K\) dưới dạng nhị phân và lần lượt nhảy theo các lũy thừa của 2 tương ứng với các bit 1 của \(K\).

Độ phức tạp

• Thời gian: Tiền xử lý \(O(N \log K_{max})\), mỗi truy vấn thực hiện trong \(O(\log K)\) bước nhảy. Với \(N, Q \le 10^5\), tổng thời gian chạy rất nhỏ (\(\approx 0.05\) giây).
• Không gian: \(O(N \log K_{max})\) bộ nhớ.

Mã nguồn C++ mẫu

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    int LOG = 62;
    vector<vector<int>> up(n, vector<int>(LOG));
    for (int i = 0; i < n; i++) {
        cin >> up[i][0];
    }
    for (int j = 1; j < LOG; j++) {
        for (int i = 0; i < n; i++) {
            up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }
    while (q--) {
        int u;
        long long k;
        cin >> u >> k;
        for (int j = 0; j < LOG; j++) {
            if (k & (1LL << j)) {
                u = up[u][j];
            }
        }
        cout << u << "\n";
    }
    return 0;
}