1. Bài toán Josephus biến thể với độ phức tạp O(n)

Trong phiên bản biến thể này của trò chơi Josephus, chúng ta có một vòng tròn gồm $n$ người được đánh số từ $1$ đến $n$. Quy tắc thay đổi như sau: ở lượt thứ $i$, người điều hành sẽ đếm $i$ người theo chiều kim đồng hồ, và người thứ $i$ được đếm sẽ bị loại. Bài toán yêu cầu tìm chỉ số của người cuối cùng còn sống sót với giới hạn $n \le 10^7$.

Để giải quyết bài toán này trong thời gian tuyến tính, chúng ta sử dụng phương pháp quy hoạch động. Gọi $f[i]$ là vị trí của người chiến thắng khi trong vòng tròn còn lại $i$ người. Khi chuyển từ trạng thái $i-1$ người sang $i$ người, chúng ta cần xác định bước nhảy (số người bị bỏ qua). Ở lượt mà vòng tròn có $i$ người, số bước đếm chính là $n - i + 1$.

Công thức truy hồi được thiết lập như sau (xét trên hệ cơ số 0 để dễ tính toán toán tử modulo):

long long solveJosephus(int n) {
    long long winner = 0; // Vị trí người thắng trong vòng tròn 1 người (0-indexed)
    for (int i = 2; i <= n; ++i) {
        int steps = n - i + 1;
        winner = (winner + steps) % i;
    }
    return winner + 1; // Chuyển về 1-indexed
}

2. Tối ưu hóa đóng góp trên cây bằng phân tách trọng tâm và FFT

Bài toán yêu cầu tính tổng đóng góp kỳ vọng của các nút trên một cây sau các thao tác xoay ngẫu nhiên. Sau khi biến đổi và phân tích dựa trên tính chất của cây phân tách trọng tâm (Centroid Decomposition), công thức tổng quát cho đóng góp của một cặp nút $(i, j)$ có thể được đưa về dạng:

Sử dụng nguyên lý bù trừ Min-Max: $a + b + \max(a, b) = (a + 1)(b + 1) - \min(a + 1, b + 1)$, ta có thể đặt $a_i = b_i + 1$ và đưa công thức về:

Phần 1: Tính toán tích $a_i \times a_j$

Phần này có thể giải quyết bằng kỹ thuật phân tách trọng tâm kết hợp với FFT (Biến đổi Fourier nhanh). Với mỗi trọng tâm, ta xây dựng đa thức dựa trên khoảng cách của các nút trong cây con đến trọng tâm. Hệ số của đa thức kết quả tại bậc $k$ sẽ cho biết tổng các tích $a_i \times a_j$ của các cặp nút có khoảng cách $k$.

Phần 2: Tính toán giá trị $\min(a_i, a_j)$

Với điều kiện ràng buộc $\sum b[i] \le 10^5$, chúng ta áp dụng kỹ thuật chia căn (thresholding):

• Với các giá trị $a_i$ lớn hơn ngưỡng $T$: Số lượng các nút này không nhiều, ta có thể duyệt trực tiếp các cặp nút và sử dụng LCA (Lowest Common Ancestor) để tính khoảng cách trong $O(1)$ sau khi tiền xử lý.
• Với các giá trị $a_i$ nhỏ hơn hoặc bằng ngưỡng $T$: Sử dụng tính chất $\min(a_i, a_j) = \sum_{k=1}^T [a_i \ge k \land a_j \ge k]$. Với mỗi giá trị $k$, ta đánh dấu các nút có $a_i \ge k$ là $1$, ngược lại là $0$, sau đó dùng FFT để đếm số lượng cặp nút có cùng khoảng cách.

Dưới đây là cấu trúc logic xử lý phần FFT cho đóng góp tích:

void computeTreeContribution(int u) {
    visited[u] = true;
    vector<double> polyNow = { (double)a[u] };
    
    for (int v : adj[u]) {
        if (visited[v]) continue;
        
        int maxD = 0;
        vector<double> polySubtree;
        getDistances(v, u, 1, maxD, polySubtree);
        
        // FFT nhân đa thức polyNow và polySubtree
        vector<double> combined = multiplyFFT(polyNow, polySubtree);
        for (int d = 0; d < combined.size(); ++d) {
            totalAns += combined[d] / (d + 1);
        }
        
        // Cập nhật polyNow để dùng cho các nhánh tiếp theo
        mergePolynomials(polyNow, polySubtree);
    }
    
    for (int v : adj[u]) {
        if (!visited[v]) {
            int nextRoot = findCentroid(v, u, subtreeSize[v]);
            computeTreeContribution(nextRoot);
        }
    }
}

Kỹ thuật này cho phép xử lý bài toán với độ phức tạp khoảng $O(T \cdot n \log^2 n + (n/T)^2)$, trong đó $T$ là ngưỡng được chọn tùy vào giới hạn bộ nhớ và thời gian (thường khoảng 15-20 cho bài toán này).