🖐️ Xin chào các bạn,

✨ Trong bài viết lần này, VNOI Wiki Project tiếp tục với chuyên đề về các giải thuật cao cấp với tổng Minkowski của các bao lồi. Bài viết là phần hai của chuỗi bài viết về hàm lồi, nối tiếp kĩ thuật “Tham đạo hàm” đã được giới thiệu vào tháng 10/2023. Tổng Minkowski là cách kết hợp hai tập hợp bằng cách lấy tất cả các điểm từ mỗi tập và cộng lại với nhau. Đối với các bao lồi, tổng Minkowski là một bao lồi mới, bao gồm tất cả các tổ hợp cộng của các điểm từ hai bao lồi ban đầu. Nó thường được dùng trong hình học và tối ưu hóa.

Trước khi tìm hiểu về chủ đề trên, độc giả cần nắm vững hàm lồi (convex function) và những khái niệm đã được nhắc đến trong bài Sum-constrained convex optimization để có thể tiếp thu kiến thức hiệu quả nhất.

🔗 Link bài viết: Tổng Minkowski

🖊️ Biên soạn: Đặng Đoàn Đức Trung - UT Austin

✅ Reviewers:

• Nguyễn Hoàng Vũ - Trường Đại học Công nghệ - ĐHQGHN
• Trần Xuân Bách - Đại học Chicago (Mỹ)

😍 Cảm ơn các bạn TNV & Admin VNOI đã biên soạn bài viết vô cùng bổ ích này. Thông qua bài viết, VNOI hy vọng rằng các bạn sẽ có thể vận dụng linh hoạt kỹ thuật trong quá trình luyện tập cũng như trong các kỳ thi sắp đến. Cảm ơn các bạn đã luôn đồng hành cùng VNOI, hẹn gặp lại các bạn trong các bài viết sau nhé!

🖐️ Xin chào các bạn,

🔥 Với phong trào lập trình thi đấu ngày càng được quan tâm, đặc biệt là trong giới học sinh, sinh viên và những người yêu thích công nghệ, việc có một nguồn tài liệu hướng dẫn chất lượng và phong phú trở nên cần thiết hơn bao giờ hết. Thấu hiểu điều này, VNOI Wiki vẫn đem đến cho cộng đồng các bài viết chất lượng cao, nội dung xúc tích với nhiều chủ đề phong phú và đa dạng. Giờ đây, VNOI Wiki khoác lên cho mình một giao diện mới với những nội dung đầy đủ về các thuật toán kèm theo độ khó, hứa hẹn đem đến cho các bạn đọc nhiều kiến thức bổ ích và là nguồn tài liệu quý giá để chuẩn bị cho các kỳ thi 💪

📝 VNOI Wiki không chỉ là một trang web chứa tài liệu lập trình, mà còn là một kho tàng kiến thức hữu ích về thuật toán, cấu trúc dữ liệu, và những kỹ năng cần thiết để tham gia các cuộc thi lập trình.

✨ Một số nội dung nổi bật của VNOI Wiki bao gồm:

• Nội dung chất lượng và mang tính chuyên môn: Tất cả các bài viết đều được viết và kiểm duyệt bởi những người có kinh nghiệm, đảm bảo tính chính xác và độ tin cậy cao.
• Kho tài liệu phong phú và đa dạng: Các bài viết tại đây bao quát nhiều chủ đề quan trọng trong lập trình và thuật toán như cấu trúc dữ liệu (cây, đồ thị, hàng đợi), các thuật toán tìm kiếm và sắp xếp, các kỹ thuật tối ưu hóa, và nhiều hơn nữa.
• Kiến thức luôn được cập nhật liên tục: Với sự đóng góp từ cộng đồng, VNOI Wiki luôn được làm mới với những kiến thức và kỹ thuật mới nhất.

😍 VNOI Wiki là một dự án tâm huyết của VNOI. Nếu bạn là một CP-er đang chuẩn bị cho các kỳ thi quan trọng sắp đến thì VNOI Wiki sẽ là một nguồn tài nguyên bạn không thể bỏ qua đấy!

👉 Xem thêm Giới thiệu về VNOI Wiki tại đây

From VNOI with love 💖

Mình có đọc ở một blog Codeforce rằng

Số node của persistent segment tree tăng lên mỗi lần update là log(n) node.

Mới đây mình gặp một bài dùng Persistent lazy segment tree và mình có thắc mắc về số node của cây này

Xin cảm ơn rất nhiều

Lời nói mở đầu : Mình là Lê Lâm lớp 11CTIN của trường THPT chuyên Lê Hồng Phong TP.HCM, đây là một trong những bài viết đầu tay của mình nên nếu phần chuẩn bị có không hay hoặc không đủ tốt mình mong được mọi người thông cảm để mình cải thiện hơn. Ngoài ra nếu có thiếu sót gì trong bài viết mong mọi người để lại cho mình biết để mình cải thiện bài viết. Cảm ơn mọi người rất nhiều.

Trước khi bắt đầu bài viết, mình nghĩ mọi người nên biết và sử dụng được một số kỹ thuật, kiến thức và cấu trúc dữ liệu để tiện theo dõi bài viết :

• Divide and Conquer (Chia để trị)
• Segment Tree (Cây phân đoạn)
• Fenwick Tree (Cây chỉ số nhị phân)
• *Convex Hull Trick (Cho phần ứng dụng 2.3)
• *FFT/NTT (Cho phần ứng dụng 2.4)

Outline

• Kỹ thuật chia để trị CDQ
• Ứng dụng của chia để trị CDQ
  • Ví dụ 1 Arnook Defensive Line
  • Ví dụ 2 CF-1093E
  • Dùng để xử lý quy hoạch động bao lồi
  • Online FFT sử dụng chia để trị CDQ
• Tổng kết
• Nguồn tham khảo (References)

1. Kỹ thuật chia để trị CDQ

Chia để trị CDQ là một kỹ thuật chia để trị được sáng tạo bởi một cp-er người Trung Quốc (viết tắt là CDQ).

Đây là một kỹ thuật xử lý các bài toán theo hướng offline. Chia để trị CDQ này gần như giống hệt chia để trị thông thường để xử lý các bài toán đếm, tìm đoạn dài nhất, ngắn nhất thỏa mãn tính chất gì đó, ...

Khác biệt giữa thuật chia để trị thông thường với chia để trị CDQ chính là việc khi ta cắt đoạn ~[l, r]~ thành hai đoạn ~[l, mid], (mid, r]~ thì lúc này, đoạn ~[l, mid]~ sẽ ảnh hưởng trực tiếp lên đoạn ~(mid, r]~. Đây là psueudo code của thuật chia để trị CDQ :

def solve(int l, int r){
        split into [l, mid], (mid, r]
        calculate the influence of [l, mid] on (mid, r]
        solve two subproblems solve(l, mid), solve(mid + 1, r)
        merge [l, mid], (mid, r]
}

Đây chỉ là framework cơ bản của thuật chia để trị CDQ nên nó sẽ khá mơ hồ, chúng ta xem qua các ví dụ các bài toán sau.

Gợi ý : Nếu trong một bài toán có cập nhật và truy vấn, nếu xử lý được bài toán tất cả cập nhật xuất hiện trước tất cả các truy vấn thì ta có thể dùng chia để trị CDQ để giải bài toán.

2. Ứng dụng của chia để trị CDQ

Ví dụ 1 (Arnook Defensive Line)

Tóm tắt đề bài :

Cho ~N~ truy vấn, mỗi truy vấn thuộc 1 trong 2 loại sau :

• ~+ \ l \ r~ : thêm một đoạn ~[l, r]~ vào tập hợp hiện tại
• ~? \ l \ r :~ đếm xem trong tập hợp hiện tại có bao nhiêu đoạn ~[x, y]~ sao cho ~x \leq l \leq r \leq y~

Tất cả kiểu dữ liệu trong bài toán đều sử dụng số nguyên dương

Giới hạn : ~1 \leq N \leq 5.10^5, 1 \leq l \leq r \leq 10^9~

Để dễ xử lý ta sẽ nén số các giá trị ~r~ trong các đoạn thẳng

Nhìn vào bài toán, chúng ta sẽ nghĩ ngay đến một số kỹ thuật phức tạp như Segment Tree 2D, Fenwick nén tọa độ hay Treap, …

Chúng ta đều công nhận rằng bài này gần như không khả thi để tìm độ phức tạp tốt hơn ~O(N \log^2 N)~ tuy nhiên chúng ta có thể cố gắng tối thiểu hóa hằng số.

Lời giải dùng chia để trị CDQ :

Đầu khi đang xử lý đoạn ~[l, r]~, chúng ta cũng sẽ chia nó ra ~[l, mid], (mid, r]~.

Giờ chúng ta sẽ thay đổi chia để trị một chút bằng cách tính contribution của các thao tác cập nhật trong đoạn ~[l, mid]~ lên những truy vấn trong ~(mid, r]~

Giờ giải bài toán dễ hơn chính là khi tất cả các operations cập nhật đều nằm trước các operations truy vấn. Để tránh sử dụng cấu trúc dữ liệu nặng thì chúng ta chỉ cần sort lại các operations cập nhật và truy vấn theo giá trị biên trái của đoạn thẳng.

Để dễ hình dung hơn, hãy xem hình sau :

Trong ví dụ này, những đoạn màu vàng sẽ là những cập nhật, và ngược lại những đoạn màu xanh sẽ là những truy vấn. Lúc này khi chia để trị, ta sẽ quan tâm những cập nhật trong đoạn ~[l, mid]~ và những truy vấn trong đoạn ~(mid, r]~.

Ta lưu chúng vào một vector và sort lại theo biên trái theo thứ tự không giảm. Ví dụ như sau :

~\text{updates} = \{[1, 10], [3, 5] \}~

~\text{queries} = \{ [3, 4], [9, 10] \}~

Ta sẽ duy trì 2 con trỏ giữa các thao tác cập nhật và truy vấn. Nếu ~l_{\text{update}} \leq l_{\text{query}}~ thì ta chỉ cần thêm ~r_{\text{update}}~ vào một cấu trúc dữ liệu dễ như Fenwick Tree / Segment Tree, sau đó ta tăng con trỏ ~\text{update}~ lên, và khi không thêm được nữa ta sẽ truy vấn bằng cách đếm số đoạn có đầu mút biên phải lớn hơn hoặc bằng đầu múc biên phải của truy vấn hiện tại.

Cứ như vậy, ta chỉ tác động vô mỗi thao tác cập nhật / truy vấn ~\log~ lần, trong mỗi lần ta cần sắp xếp chúng nên độ phức tạp sẽ là ~O(N \log^2 N)~. Tuy nhiên so với thực tế, nó chạy rất nhanh vì hằng số cho hàm sắp xếp rất nhỏ và hằng số của Fenwick Tree lại càng tối ưu. Vì vậy thuật toán ta có được chạy nhanh hơn các thuật toán sử dụng các cấu trúc dữ liệu nặng như Segment Tree 2D hay cây Fenwick 2D được nén số.

Code

#include<bits/stdc++.h>

using namespace std;

const int MAX = 5e5 + 5;

int n, x[MAX], y[MAX], ans[MAX];
char c[MAX];
vector<int> val;

struct Fenwick{
    vector<int> bit;
    Fenwick(int n) : bit(n + 1, 0) {}

    void update(int id, int val){
        for(; id > 0; id -= id & (-id)){
            bit[id] += val;
        }
    }

    int query(int id){
        int sum = 0;
        for(; id < (int)bit.size(); id += id & (-id)){
            sum += bit[id];
        }
        return sum;
    }
};

void solve(int l, int r, Fenwick& fenwick){
    if(l >= r) return;
    int mid = l + r >> 1;

    vector<int> updates, queries;

    for(int i = l; i <= mid; ++i) if(c[i] == '+') updates.push_back(i);
    for(int i = mid + 1; i <= r; ++i) if(c[i] == '?') queries.push_back(i);

    sort(updates.begin(), updates.end(), [&](int i, int j){ return x[i] < x[j]; });
    sort(queries.begin(), queries.end(), [&](int i, int j){ return x[i] < x[j]; });

    vector<int> save;
    for(int i = 0, j = 0; i < (int)queries.size(); ++i){
        while(j < (int)updates.size() && x[updates[j]] <= x[queries[i]]){
            fenwick.update(y[updates[j]], +1);
            save.push_back(y[updates[j]]);
            ++j;
        }

        ans[queries[i]] += fenwick.query(y[queries[i]]);
    }

    while(!save.empty()){
        fenwick.update(save.back(), -1);
        save.pop_back();
    }

    solve(l, mid, fenwick);
    solve(mid + 1, r, fenwick);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> c[i] >> x[i] >> y[i];
        val.push_back(y[i]);
    }

    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());

    for(int i = 0; i < n; ++i){
        y[i] = lower_bound(val.begin(), val.end(), y[i]) - val.begin() + 1;
    }

    int sz = (int)val.size();
    Fenwick fenwick(sz);

    solve(0, n - 1, fenwick);
    for(int i = 0; i < n; ++i){
        if(c[i] == '?') cout << ans[i] << '\n';
    }

    return 0;
}

Thông thường khi sử dụng chia để trị, hầu hết chia để trị dùng để tính đáp án cho bài toán, còn chia để trị CDQ sẽ tính contribution của những đoạn trước lên đáp án.

~\\~

2.2 Ví dụ 2 (CF-1093E)

Tóm tắt đề bài : Cho hai dãy ~a, b~ là hai hoán vị có độ dài ~n~. Bạn có ~m~ thao tác, mỗi thao tác thuộc 1 trong 2 loại :

1. ~l_1 \ r_1 \ l_2 \ r_2~ : Đếm số các giá trị cùng xuất hiện trong hai dãy con liên tiếp ~a[l_1...r_1]~ và ~b[l_2...r_2]~
2. ~x \ y~ : Đổi vị trí ~b_x~ và ~b_y~

Giới hạn : ~1 \leq n, m \leq 2.10^5, 1 \leq l_1 \leq r_1 \leq n, 1 \leq l_2 \leq r_2 \leq n~

Lời giải gợi ý : Đầu tiên ta sẽ cố gắng thay đổi bài toán một chút, gợi ~pos_a(i)~ là vị trí của giá trị ~i~ xuất hiện trong dãy ~a~, tương tự với ~pos_b(i)~ Đưa lên thành tọa độ điểm ~(pos_a(i), pos_b(i))~ và bây giờ, khi gặp các truy vấn chúng ta thấy rằng nó chính là bài toán đếm số điểm ~(pos_a(i), pos_b(i))~ nằm trong bảng con ~(l_1, l_2)~ tới bảng con ~(r_1, r_2)~
Bài toán bây giờ được biến đổi đơn giản hơn là

1. Cho một số thao tác cập nhật vị trí điểm (-1 hoặc +1)
2. Cho một số truy vấn trên bảng con từ ~(x_1, y_1)~ đến ~(x_2, y_2)~

Ban đầu ta sẽ thêm lần lượt ~n~ điểm ~(pos_a(i), pos_b(i))~ vào CTDL

Với truy vấn cập nhật, chúng ta thấy chỉ cần 4 lần update bằng cách thêm 2 truy vấn update -1 tại các vị trí cũ, và 2 truy vấn +1 tại các vị trí mới sau khi swap ~pos_b(b_x)~ với ~pos_b(b_y)~

Còn với truy vấn tính tổng bảng con, chúng ta sẽ dùng ý tưởng của prefix sum 2D, kết hợp việc duy trì 2 con trỏ trên các thao tác chúng ta sẽ đạt được độ phức tạp ~\text{O}(4m \log^2 n)~

Đây chính là một trong những ứng dụng cơ bản nhất của chia để trị CDQ, chính là việc tránh sử dụng các CTDL 2D để xử lý mà thay bằng các cấu trúc dữ liệu 1D kết hợp chia để trị để giảm hằng số sử dụng.

Code

#include<bits/stdc++.h>

using namespace std;

const int MAX = 2e5 + 5;

int n, q, a[MAX], b[MAX], posa[MAX], posb[MAX], ans[MAX];

struct Fenwick{
    vector<int> bit;
    Fenwick(int n) : bit(n + 1, 0) {}

    void update(int id, int val){
        for(; id < (int)bit.size(); id += id & (-id)){
            bit[id] += val;
        }
    }

    int query(int id){
        int sum = 0;
        for(; id > 0; id -= id & (-id)){
            sum += bit[id];
        }
        return sum;
    }
};

struct event{
    int x, y, id, type;
};

void solve(int l, int r, vector<event>& events, Fenwick& fenwick){
    if(l >= r) return;
    int mid = l + r >> 1;

    vector<int> updates, queries;
    for(int i = l; i <= mid; ++i){
        if(events[i].id == 0) updates.push_back(i);
    }

    for(int i = mid + 1; i <= r; ++i){
        if(events[i].id != 0) queries.push_back(i);
    }

    sort(updates.begin(), updates.end(), [&](int i, int j){ return events[i].x < events[j].x; });
    sort(queries.begin(), queries.end(), [&](int i, int j){ return events[i].x < events[j].x; });

    vector<pair<int, int>> saves;
    for(int i = 0, j = 0; i < (int)queries.size(); ++i){
        while(j < (int)updates.size() && events[updates[j]].x <= events[queries[i]].x){
            saves.push_back({events[updates[j]].y, events[updates[j]].type});
            fenwick.update(events[updates[j]].y, events[updates[j]].type);
            ++j;
        }

        ans[events[queries[i]].id] += events[queries[i]].type * fenwick.query(events[queries[i]].y);
    }

    while(!saves.empty()){
        fenwick.update(saves.back().first, -saves.back().second);
        saves.pop_back();
    }

    solve(l, mid, events, fenwick);
    solve(mid + 1, r, events, fenwick);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q;
    for(int i = 1; i <= n; ++i) cin >> a[i], posa[a[i]] = i;
    for(int i = 1; i <= n; ++i) cin >> b[i], posb[b[i]] = i;

    vector<event> events;
    for(int i = 1; i <= n; ++i){
        events.push_back({posa[i], posb[i], 0, +1});
    }

    int idQueries = 0;
    for(int i = 1; i <= q; ++i){
        int type;
        cin >> type;
        if(type == 1){
            int l1, r1, l2, r2;
            cin >> l1 >> r1 >> l2 >> r2;

            ++idQueries;
            events.push_back({r1, r2, idQueries, +1});
            if(l1 > 1 && l2 > 1) events.push_back({l1 - 1, l2 - 1, idQueries, +1});
            if(l1 > 1) events.push_back({l1 - 1, r2, idQueries, -1});
            if(l2 > 1) events.push_back({r1, l2 - 1, idQueries, -1});
        } else{
            int x, y;
            cin >> x >> y;

            int vx = b[x], vy = b[y];
            events.push_back({posa[vx], posb[vx], 0, -1});
            events.push_back({posa[vy], posb[vy], 0, -1});
            swap(b[x], b[y]);
            swap(posb[vx], posb[vy]);
            events.push_back({posa[vx], posb[vx], 0, +1});
            events.push_back({posa[vy], posb[vy], 0, +1});
        }       
    }

    Fenwick fenwick(n);
    solve(0, (int)events.size() - 1, events, fenwick);   
    for(int i = 1; i <= idQueries; ++i){
        cout << ans[i] << '\n';
    }

    return 0;
}

~\\~

2.3 Dùng để xử lý quy hoạch động bao lồi

Tóm tắt đề bài :

Có ~N~ hòn đá được đánh số từ 1 tới 𝑁. Hòn đá thứ ~i~ có chiều cao ~h_i~.

Có một chú ếch khởi đầu ở hòn đá thứ ~1~ và nó sẽ lặp lại các hành động như sau để đến được hòn đá thứ ~N~:

• Nếu nó đang ở vị trí ~i~, và khi nhảy tới vị trí ~j \ (i < j)~ thì nó sẽ mất chi phí là ~(h_i - h_j)^2 + C~

Hãy tìm chi phí nhỏ nhất có thể để chú ếch đến được hòn đá thứ ~N~.

Giới hạn : ~1 \leq N \leq 2.10^5~, ~1 \leq h_i \leq 10^6, 1 \leq C \leq 10^{12}~

~\\~

Lời giải :

Gọi ~\text{dp}_i~ là chi phí nhỏ nhất để con ếch nhảy từ ~1~ đến vị trí thứ ~i~, ta có base-case ~\text{dp}_1 = 0~ Giả sử lượt trước đó, con ếch đang ở hòn đá thứ ~j \ (1 \leq j < i)~, thì bây giờ chi phí mới sẽ là ~\text{dp}_j + (h_i - h_j)^2 + C~. Từ đó công thức truy hồi để tính ~\text{dp}_i~ là :

$$\text{dp}_i = \min_{j = 1}^{i - 1} (\text{dp}_j + (h_i - h_j)^2 + C)$$ Viết lại công thức để dễ nhìn hơn, nó sẽ là : $$\text{dp}_i = h_i^2 + C + \min_{j = 1}^{i - 1} (\text -2h_ih_j + \text{dp}_j + h_j^2)$$

Lúc ta thấy nếu quy lại bài toán có ~i - 1~ đường thẳng dạng ~y = ax + b~ với hệ số góc ~a = -2h_j~, hệ số tự do ~b = \text{dp}_j + h_j^2~ Thì lúc này nó sẽ là truy vấn tìm giá trị nhỏ nhất của ~y = ax + b~ với hoành độ ~x = h_i~.

Đây chính là bài toán kinh điển của Convex hull trick, nhưng bài toán cần xử dụng dạng Fully Dynamic (Một dạng rất khó cài và rất mạo hiểm trong phòng thi) vì các hệ số góc là ngẫu nhiên và bạn chỉ biết sử dụng dạng cơ bản dạng đó là hệ số góc của các đường thẳng được sắp xếp ? (Thật ra bài toán có thể còn nhiều cách giải như dùng Li-Chao Tree nhưng mình chỉ sẽ đề cập về Convex hull trick sử dụng kỹ thuật này)

Chia để trị CDQ chính là một cách để xử lý của bài toán.

Cũng như những ví dụ trên, gọi ~\text{solve}(l, r)~ là hàm chia để trị. Lúc này đặc biệt hơn một chút, ta sẽ gọi đây là hàm để tính những giá trị ~\text{dp}(i)~ với ~l \leq i \leq r~.

Để dễ hình dung hơn, mọi người hãy xét trường hợp ~n = 8~ vào vị trí ~i = 6~ là vị trí cần tính ~\text{dp}(6)~. Chúng ta chỉ sẽ quan tâm những lần ta chia để trị chứa ~i = 6~ để tiện mô tả.

Trong lần gọi hàm chia để trị đoạn ~\text{solve}(1, 8)~ :

Như chúng ta có thể thấy, các giá trị ~\text{dp}_j~ trong đoạn ~[1, 4]~ sẽ được đóng góp vào giá trị ~\text{dp}_6~

Tiếp theo là lầ chia để trị ở đoạn ~\text{solve}(5, 8)~ :

Kế tiếp, do trong lần chia để trị này, các giá trị ~\text{dp}_j~ trong đoạn ~[5, 6]~ sẽ đóng góp vào đoạn ~[7, 8]~ nên bản chất giá trị ~\text{dp}_6~ chưa được đóng góp thêm

Ở lần chia để trị đoạn ~\text{solve}(5, 6)~ :

Lần này, ~\text{dp}_5~ trong đoạn ~[5, 5]~ sẽ đóng góp vào đoạn ~[6, 6]~ và như vậy, ta thấy đoạn ~[1, i - 1]~ đã được đóng góp đủ vào giá trị ~\text{dp}_i~.

Psueudo code :

set dp[1] = 0, dp[2] = inf, dp[3] = inf, ..., dp[n] = inf
def solve(l, r){
        if(l == r) return;
        mid = (l + r) / 2;

        solve(l, mid);

        vector<line> lines;
        for(int i : l -> mid) : 
                lines.push_back(); 

        sort(lines, by_slope);
        insert_all_lines_to_convex_hull();

        for(int i : mid + 1 -> r) : 
                dp[i] = min(dp[i], query_point());
        solve(mid + 1, r);
}

Đây chính là phần code gợi ý để sử dụng convex hull trick ở dạng hệ số góc ngẫu nhiên nhưng không cần dùng cấu trúc dữ liệu nặng. Độ phức tạp ~\text{O}(n \log^2 n)~, hằng số bài toán trong trường hợp này chấp nhận được so với thuật ~\text{O}(n^2)~ hay một thuật ~\text{O}(n \log n)~ mạo hiểm.

~\\~

2.4 Online FFT sử dụng chia để trị CDQ

Đây là một kỹ thuật khá được sử dụng trong các bài toán sử dụng đa thức, FFT và đặc biệt được các kỳ thi ICPC rất ưa chuộng.

Đề bài : Cho biết trước ~\text{G}(0), \text{G}(1), ..., \text{G}(n)~. Định nghĩa hàm ~\text{F}(i) :~

$$\text{F}(0) = 1, \text{F}(i) = \sum_{j = 0}^{i - 1} \text{F}(j) \text{G}(n - j) \ (i \geq 1)$$

Yêu cầu tính ~\text{F}(n) \bmod 998244353~

Giới hạn : ~1 \leq n \leq 10^5, 0 \leq \text{G}(i) < 998244353~

Khi nhìn vào ~\text{F}(i) = \sum_{j = 0}^{i - 1} \text{F}(j) \text{G}(n - j)~, chúng ta có một cảm giác nó rất giống một chút gì đó với thuật toán FFT/NTT.

Để giới thiệu sơ qua về FFT/NTT là gì (Vì đây không phải là bài viết về FFT nên mình chỉ nói sơ qua công dụng của thuật toán này) :

• Cho 2 dãy thức bậc ~n~ là ~\text{A}(x) = \text{A}_0 + \text{A}_1x + \text{A}_2x^2 + ... \text{A}_{n - 1}x^{n - 1}~ và ~\text{B}(x) = \text{B}_0 + \text{B}_1x + \text{B}_2x^2 + ... \text{B}_{n - 1}x^{n - 1}~
• Ta có phép nhân giữa hai đa thức ~A(x)~ và ~B(x)~ có kết quả là một đa thức ~\text{C}(x) = \sum_{i = 0}^n \sum_{j = 0}^n \text{A}_i \text{B}_j x^{i + j}~ với các hệ số tại ~x^k~ là ~\text{C}_k = \sum_{i + j = k} \text{A}_i \text{B}_j~
• NTT là chính là FFT nhưng có sử dụng phép modulo.
• Độ phức tạp của thuật toán FFT/NTT là ~\text{O}(n \log n)~ cho phép tích của hai đa thức ~\text{A}(x)~ và ~\text{B}(x)~ như đã mô tả.

Cũng như bài toán chia để trị CDQ kết hợp bao lồi, ta cũng sẽ gọi ~\text{solve}(l, r)~ là hàm chia để trị để tính các ~\text{F}(i)~ với ~l \leq i \leq r~.

Sau đó khi chuyển sang tính contribution của ~[l, mid]~ lên ~(mid, r]~ chúng ta sẽ viết lại như sau

~\text{contribF}(i) = \sum_{l \leq u \leq mid, u + v = i} \text{F}(u) G(v) \ (mid < i \leq r)~

Lúc này trong đây lại chính là một lần nhân FFT, gọi :

• ~\text{A}(x) = \text{G}(0) + \text{G}(1)x^1, \text{G}(2)x^2, ..., \text{G}(r - l + 1)x^{r - l + 1}~.
• ~\text{B}(x) = \text{F}(l) + \text{F}(l + 1)x^1 + \text{F}(l + 2)x^2 + ... + \text{F}(mid)x^{mid - l}~.
• ~\text{C}(x)~ là tích của hai đa thức trên. Do ở đây chúng ta chỉ thêm các ~\text{F}_i~ với ~i \in [l, mid]~ vào đa thức ~\text{B}(x)~ (Vì nếu thêm luôn cả ~l - 1~ số ~0~ ở đầu sẽ khiến cho bài toán có độ phức tạp là ~\text{O}(n^2 \log n)~). và vì vậy nên ~\text{contribF(i)} = \text{C}_{i - l}~. Sau đó ta sẽ chia để trị tiếp và cộng dần lại để tính tiếp ~\text{F}(mid + 1), \text{F}(mid + 2), ... \text{F}(r)~

Psueudo code :

def onlineFFT(l, r){
        if(l == r){
                if(l == 0) f[l] = 1;
                return;
        }

        mid = (l + r) / 2;
        onlineFFT(l, mid);

        vector<int> A, B;
        for(int i : 0 -> r - l + 1) A.push_back(g[i]);
        for(int i : l -> mid) B.push_back(f[i]);

        vector<int> contribF = conv(A, B); //conv(A, B) is the convolution of 2 polynomials
        for(int i : mid + 1 -> r) : 
                f[i] += contribF[i - l];
        onlineFFT(mid + 1, r);
}

Độ phức tạp cuối cùng chúng ta nhận được với FFT online sẽ là ~\text{O}(n \log^2 n)~. (Ngoài ra FFT online còn có thể được giải không cần chia để trị với cùng độ phức tạp, mọi người có thể tham khảo blog này FFT online bằng chia bit) ~\\~

3. Tổng kết

Như vậy chúng ta đã điểm qua một số ứng dụng của chia để trị CDQ trong Lập trình thi đấu, đây là một kỹ thuật không khó học và rất tiện lợi trong một số trường hợp cần xử lý nhiều cấu trúc dữ liệu nặng nhưng vẫn muốn đảm bảo độ phức tạp tốt nhất có thể.

Mong sau bài viết này mọi người sẽ nắm được phần nào kỹ thuật này và áp dụng được nó trong những lúc cần thiết nhé.

4. Nguồn tham khảo (References)

https://tanujkhattar.wordpress.com Online FFT

https://github.com/ShahjalalShohag/code-library/blob/main/Math/NTT Online (D%26C).cpp

https://robert1003.github.io/2020/01/31/cdq-divide-and-conquer.html

https://mzhang2021.github.io/cp-blog/divide-and-conquer/

Vòng chung kết VNOI CUP tại TP.HCM đã kết thúc cũng là lúc hành trình VNOI CUP 2024 chính thức khép lại. Để có được 1 chặng đua dài và thành công, đem lại nhiều cung bậc cảm xúc như vậy, BTC xin gửi lời cảm ơn vô cùng sâu sắc tới:

🌟 Về phía đơn vị bảo trợ, BTC xin chân thành gửi lời cảm ơn tới Hội Tin học Việt Nam. Sự bảo trợ của quý Hội đã khẳng định chất lượng, giá trị và uy tín của VNOI CUP, nâng kỳ thi lên một tầm cao mới.

🌟 Về phía đơn vị đăng cai, BTC xin chân thành cảm ơn toàn thể ban giám hiệu, các thầy cô giáo và các bạn sinh viên của Trường ĐH Khoa học tự nhiên, ĐHQG-HCM đã tận tình giúp đỡ, hỗ trợ VNOI hiện thực hoá kỳ thi này.

🌟 Đặc biệt, về phía nhà tài trợ, BTC xin chân thành cảm ơn Nhà tài trợ chính của cả 3 mùa VNOI CUP vừa qua - Công ty cổ phần FPT - tập đoàn công nghệ mang quy mô toàn cầu. Sự ủng hộ từ quý công ty không chỉ mang ý nghĩa vật chất, mà còn góp phần khẳng định rằng, cuộc thi đã gián tiếp đào tạo ra những nhân lực chất lượng cao cho công cuộc chuyển đổi số.

🌟 Cùng với đó, BTC cũng vô cùng vui mừng và trân trọng cảm ơn sự hiện diện của các thầy, các anh là những ngọn cờ đầu, đạt những thành tích cao trong các kỳ thi quốc tế đã ủng hộ tới tham dự Chung kết VNOI CUP 2024.

🌟 Và cũng không thể quên gửi lời cảm ơn các cơ quan báo chí và truyền thông đã mang VNOI CUP tới mọi miền tổ quốc.

❤️ Cuối cùng, xin gửi lời cảm ơn tới tất cả các bạn đã quan tâm theo dõi và ủng hộ VNOI CUP 2024. Hẹn gặp lại tại VNOI CUP 2025!!

✨ Chỉ còn chưa đầy 24h nữa thôi, cơ hội cuối cùng để tham dự vòng chung kết VNOI CUP 2024 diễn ra tại TPHCM sẽ kết thúc! Các bạn ứng viên hãy nhanh tay đăng ký tham gia Bảng mở rộng ngay hôm nay để chạm tay đến nhiều món quà ấn tượng tại chặng cuối cùng VNOI CUP 2024 nhé!

✨ Bảng mở rộng Chung kết VNOI CUP 2024 Bảng mở rộng sẽ được tổ chức song song với bảng thi của 24 thí sinh tham gia Chung kết chính thức tại Trường ĐH Khoa học tự nhiên. BTC sẽ cung cấp nước uống và đồ ăn nhẹ cho thí sinh trong quá trình thi.

🖊️ Form đăng ký: Xem tại đây

🖊️ Thời hạn đăng ký: ~ 23h59'~ ngày ~22/07/2024~

🖊️ Thể lệ:

• Bảng thi đấu sẽ có tối đa 30 thí sinh tham dự. Sau khi nhận đơn đăng ký, BTC sẽ chọn ra danh sách thí sinh tham dự (ưu tiên theo thứ hạng tổng điểm 2 vòng loại) và gửi email phản hồi cho thí sinh.

• Thí sinh mang theo laptop cá nhân để làm bài.

• Chi phí dự thi:

  • Bảng mở rộng KHÔNG thu phí đăng ký.

  • Thí sinh tự chủ động chi phí di chuyển, ăn uống và địa điểm lưu trú.

✨ Các thí sinh bảng mở rộng sẽ được nhận giấy chứng nhận và cùng tham gia các hoạt động chung do BTC bố trí.

🙌 Đừng bỏ lỡ cơ hội duy nhất được thi đấu cùng 24 'anh tài' tại Bảng mở rộng của chung kết VNOI CUP 2024 nhé! Hẹn gặp lại bạn vào ngày 01/08 - 04/08 tại thành phố mang tên Bác ✨