Khóa học CTDL và GT

Bài 28.1. Khái niệm và nguyên lý DP Bitmask

Chào mừng quay trở lại với series về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ lặn sâu vào một kỹ thuật Lập trình Động (Dynamic Programming) nâng cao và cực kỳ hữu ích khi gặp các bài toán liên quan đến tập hợp con (subset) hoặc các ràng buộc phức tạp giữa các phần tử: DP Bitmask.

Nếu bạn đã nắm vững kiến thức cơ bản về DP, DP Bitmask sẽ là một bước tiến thú vị. Nó kết hợp sức mạnh của Lập trình Động trong việc giải các bài toán tối ưu có cấu trúc con gối nhau và tính tối ưu cục bộ, với sự khéo léo của thao tác bit để biểu diễn trạng thái của bài toán một cách gọn gàng và hiệu quả.

Tại Sao Lại Cần Bitmask Trong DP?

Trong nhiều bài toán DP truyền thống, trạng thái (state) thường được biểu diễn bằng một hoặc nhiều chỉ số (index) đơn giản, ví dụ dp[i] (tối ưu đến phần tử thứ i), dp[i][j] (tối ưu trên đoạn từ i đến j hoặc dùng i phần tử và đạt trạng thái j). Tuy nhiên, có những bài toán mà trạng thái của chúng ta cần lưu trữ thông tin về việc một tập hợp các phần tử nào đó đã được xử lý hay chưa.

Ví dụ:

• Bạn cần thăm tất cả các thành phố trong một danh sách, và thứ tự thăm quan quan trọng. Trạng thái cần biết: những thành phố nào đã thăm và thành phố cuối cùng đã thăm là thành phố nào.
• Bạn cần chọn một tập hợp các nhiệm vụ sao cho tổng giá trị lớn nhất, với ràng buộc là một nhiệm vụ chỉ có thể chọn sau khi một tập hợp các nhiệm vụ khác đã hoàn thành. Trạng thái cần biết: những nhiệm vụ nào đã được hoàn thành.
• Bạn cần ghép N người với N công việc sao cho tổng chi phí nhỏ nhất. Trạng thái cần biết: những công việc nào đã được giao (cho những người đầu tiên).

Lúc này, việc biểu diễn "tập hợp các phần tử đã được xử lý" trở nên khó khăn nếu chỉ dùng các chỉ số thông thường. Đây là lúc Bitmask tỏa sáng.

Một Bitmask đơn giản là một số nguyên, trong đó mỗi bit của số nguyên đó đại diện cho trạng thái của một phần tử cụ thể. Ví dụ, nếu chúng ta có N phần tử, ta có thể dùng một số nguyên 32-bit hoặc 64-bit. Bit thứ i (thường tính từ 0) của số nguyên đó sẽ đại diện cho phần tử thứ i.

• Nếu bit thứ i là 1: Phần tử thứ i nằm trong tập hợp/đã được xử lý/đã được chọn.
• Nếu bit thứ i là 0: Phần tử thứ i không nằm trong tập hợp/chưa được xử lý/chưa được chọn.

Với N phần tử, chúng ta có thể biểu diễn tất cả 2^N tập hợp con khác nhau chỉ bằng các số nguyên từ 0 đến 2^N - 1. Số 0 đại diện cho tập rỗng, số (1 << N) - 1 (hay (1 << N) - 1) đại diện cho tập hợp chứa tất cả N phần tử.

Vì mỗi tập hợp con có thể được biểu diễn bằng một số nguyên duy nhất, chúng ta có thể sử dụng số nguyên này làm một phần của chỉ số trạng thái trong mảng DP của mình. Đây chính là cốt lõi của DP Bitmask.

Nguyên lý hoạt động của DP Bitmask

Nguyên lý chung của DP Bitmask là xây dựng trạng thái DP dựa trên các bitmask, thường có dạng dp[mask] hoặc dp[mask][...].

1. Định nghĩa Trạng thái: Trạng thái dp[mask] (hoặc tương tự) thường lưu trữ giá trị tối ưu (chi phí nhỏ nhất, giá trị lớn nhất, số cách,...) để đạt được một tình huống mà tập hợp các phần tử được biểu diễn bởi mask đã được xử lý. Các chỉ số khác (nếu có, ví dụ dp[mask][last_element]) bổ sung thông tin cần thiết về tình huống đó.

2. Trạng thái Cơ sở (Base Case): Xác định trạng thái ban đầu đơn giản nhất và giá trị DP tương ứng. Ví dụ: dp[0] (tập rỗng) thường có giá trị 0 hoặc một giá trị ban đầu phù hợp.

3. Chuyển trạng thái (Transitions): Duyệt qua các trạng thái DP theo một thứ tự nhất định (thường là tăng dần theo giá trị của mask). Từ một trạng thái dp[mask] hiện tại, ta xem xét việc thêm một phần tử mới i vào tập hợp. Nếu phần tử i chưa có trong mask (tức bit thứ i của mask bằng 0), ta có thể chuyển sang trạng thái mới mask_moi = mask | (1 << i). Giá trị dp[mask_moi] sẽ được cập nhật dựa trên dp[mask] và chi phí/lợi ích của việc thêm phần tử i. Việc cập nhật thường là tìm min/max: dp[mask_moi] = min(dp[mask_moi], dp[mask] + cost_of_adding_i).

   • Lưu ý: Thao tác (1 << i) tạo ra một số nguyên chỉ có bit thứ i là 1, các bit khác bằng 0.
   • Lưu ý: Thao tác mask | (1 << i) bật bit thứ i trong mask, tức là thêm phần tử i vào tập hợp.
   • Lưu ý: Để kiểm tra xem phần tử i có trong mask hay không, ta dùng (mask & (1 << i)). Kết quả khác 0 nếu bit i là 1, bằng 0 nếu bit i là 0.

4. Kết quả Cuối cùng: Kết quả của bài toán thường nằm ở trạng thái dp[(1 << N) - 1] (mask biểu diễn tập hợp tất cả N phần tử) hoặc cần duyệt qua một số trạng thái cuối cùng để tìm giá trị tối ưu.

Ưu điểm: Biểu diễn trạng thái tập hợp con cực kỳ nhỏ gọn. Nhược điểm: Số lượng trạng thái là 2^N. Do đó, DP Bitmask chỉ hiệu quả khi số lượng phần tử N nhỏ, thường là N <= 20 (vì 2^20 khoảng 1 triệu, O(N 2^N) hoặc O(N^2 2^N) vẫn có thể chấp nhận được). Với N lớn hơn, cần tìm giải pháp khác.

Để hiểu rõ hơn, chúng ta sẽ đi vào một vài ví dụ kinh điển.

Ví dụ 1: Bài toán Người du lịch đơn giản (Simple TSP-like)

Bài toán: Cho N thành phố (đánh số từ 0 đến N-1) và ma trận chi phí di chuyển cost[i][j] từ thành phố i đến thành phố j. Tìm chi phí nhỏ nhất để thăm tất cả các thành phố, bắt đầu từ thành phố 0. (Đây là một biến thể đơn giản, không yêu cầu quay về thành phố ban đầu).

Phân tích: Chúng ta cần biết những thành phố nào đã thăm và thành phố cuối cùng đã dừng chân là thành phố nào để có thể tính chi phí đi tiếp.

• "Những thành phố nào đã thăm" -> dùng bitmask.
• "Thành phố cuối cùng đã dừng chân" -> dùng một chỉ số khác.

Định nghĩa trạng thái: dp[mask][last_city] là chi phí nhỏ nhất để thăm tập hợp các thành phố được biểu diễn bởi mask, với thành phố cuối cùng trong hành trình là last_city.

Kích thước mảng DP sẽ là dp[1 << N][N].

Trạng thái cơ sở: Bắt đầu từ thành phố 0. Ban đầu, chúng ta chỉ thăm duy nhất thành phố 0. dp[1 << 0][0] = 0. (Mask 1 << 0 là 1, bit thứ 0 bật, biểu thị chỉ thăm thành phố 0). Tất cả các trạng thái dp[mask][last_city] khác ban đầu sẽ được gán một giá trị vô cùng lớn (ví dụ INT_MAX hoặc LLONG_MAX) để thể hiện rằng không thể đạt được trạng thái đó hoặc chưa được tính toán.

Chuyển trạng thái: Duyệt qua tất cả các mask từ 1 đến (1 << N) - 1. Duyệt qua tất cả các thành phố u từ 0 đến N-1. Nếu bit thứ u trong mask đang bật (nghĩa là thành phố u có trong tập hợp mask), và dp[mask][u] không phải là vô cùng lớn (nghĩa là trạng thái này có thể đạt được), ta xem xét việc đi từ thành phố u đến một thành phố v chưa được thăm. Một thành phố v (từ 0 đến N-1) là chưa được thăm nếu bit thứ v trong mask đang tắt: !(mask & (1 << v)). Nếu đi từ u đến v, mask mới sẽ là mask_moi = mask | (1 << v). Chi phí sẽ tăng thêm cost[u][v]. Ta cập nhật trạng thái mới: dp[mask_moi][v] = min(dp[mask_moi][v], dp[mask][u] + cost[u][v]).

Kết quả cuối cùng: Sau khi duyệt hết tất cả các mask, chi phí nhỏ nhất để thăm tất cả các thành phố sẽ là giá trị nhỏ nhất trong số dp[(1 << N) - 1][i] với mọi i từ 0 đến N-1 (vì ta có thể kết thúc hành trình ở bất kỳ thành phố nào sau khi đã thăm tất cả).

Code minh họa (C++):

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits> // For INT_MAX or LLONG_MAX

using namespace std;

const int INF = 1e9; // Sử dụng một giá trị lớn cho vô cùng

int main() {
    int N; // Số lượng thành phố
    cout << "Nhap so luong thanh pho (N <= 20): ";
    cin >> N;

    if (N > 20) {
        cout << "N qua lon, DP Bitmask khong hieu qua!" << endl;
        return 1;
    }

    vector<vector<int>> cost(N, vector<int>(N));
    cout << "Nhap ma tran chi phi di chuyen (" << N << "x" << N << "):" << endl;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> cost[i][j];
        }
    }

    // dp[mask][last_city]: chi phi nho nhat de tham tap thanh pho trong mask, ket thuc o last_city
    vector<vector<int>> dp(1 << N, vector<int>(N, INF));

    // Base case: Bat dau tu thanh pho 0
    // Mask 1 << 0 co bit 0 bat, cac bit khac tat, bieu thi chi tham thanh pho 0
    dp[1][0] = 0;

    // Duyet qua tat ca cac mask (tu 1 den 2^N - 1)
    for (int mask = 1; mask < (1 << N); ++mask) {
        // Duyet qua tat ca cac thanh pho co the la diem ket thuc cua mask hien tai
        for (int u = 0; u < N; ++u) {
            // Neu thanh pho u co trong mask (bit thu u bat)
            // va trang thai dp[mask][u] co the dat duoc (khac INF)
            if ((mask & (1 << u)) && dp[mask][u] != INF) {
                // Duyet qua tat ca cac thanh pho co the di tiep den (thanh pho v)
                for (int v = 0; v < N; ++v) {
                    // Neu thanh pho v CHUA co trong mask (bit thu v tat)
                    if (!(mask & (1 << v))) {
                        // Mask moi sau khi di den v: bat bit v
                        int next_mask = mask | (1 << v);
                        // Cap nhat chi phi cho trang thai moi
                        // dp[next_mask][v] = min(dp[next_mask][v], dp[mask][u] + cost[u][v])
                        dp[next_mask][v] = min(dp[next_mask][v], dp[mask][u] + cost[u][v]);
                    }
                }
            }
        }
    }

    // Tim ket qua cuoi cung: chi phi nho nhat khi da tham tat ca cac thanh pho ((1 << N) - 1)
    // Ket thuc o bat ky thanh pho nao (tu 0 den N-1)
    int min_cost = INF;
    int final_mask = (1 << N) - 1; // Mask voi tat ca cac bit bat

    for (int i = 0; i < N; ++i) {
        min_cost = min(min_cost, dp[final_mask][i]);
    }

    if (min_cost == INF) {
        cout << "Khong the tham het tat ca cac thanh pho." << endl;
    } else {
        cout << "Chi phi nho nhat de tham tat ca cac thanh pho bat dau tu thanh pho 0 la: " << min_cost << endl;
    }

    return 0;
}

Giải thích code:

• Chúng ta khởi tạo mảng dp có kích thước (1 << N) hàng và N cột với giá trị INF (vô cùng lớn). dp[mask][last_city] lưu chi phí.
• dp[1][0] = 0: Trạng thái cơ sở, mask 1 (binary ...0001) chỉ có bit 0 bật, biểu thị chỉ thăm thành phố 0. Ta bắt đầu ở thành phố 0, chi phí 0.
• Vòng lặp for (int mask = 1; mask < (1 << N); ++mask): Duyệt qua tất cả các trạng thái tập hợp con có thể, từ 1 (chỉ thăm thành phố 0) đến (1 << N) - 1 (thăm tất cả các thành phố).
• Vòng lặp for (int u = 0; u < N; ++u): Với mỗi mask, ta xem xét thành phố u có thể là điểm kết thúc hiện tại.
• if ((mask & (1 << u)) && dp[mask][u] != INF): Kiểm tra xem thành phố u có thực sự nằm trong tập hợp mask hay không (mask & (1 << u) khác 0) và liệu trạng thái dp[mask][u] có giá trị hợp lệ (không phải INF) hay không.
• Vòng lặp for (int v = 0; v < N; ++v): Từ thành phố u, ta xem xét việc di chuyển đến thành phố v.
• if (!(mask & (1 << v))): Kiểm tra xem thành phố v đã chưa được thăm trong mask hiện tại hay không. mask & (1 << v) sẽ là 0 nếu bit v tắt. Dấu ! đảo ngược điều kiện, kiểm tra bit v tắt.
• int next_mask = mask | (1 << v);: Nếu v chưa được thăm, mask mới sau khi thăm cả v sẽ là mask cũ OR với mask chỉ có bit v bật (1 << v). Phép OR (|) sẽ bật bit v trong mask.
• dp[next_mask][v] = min(dp[next_mask][v], dp[mask][u] + cost[u][v]);: Cập nhật chi phí nhỏ nhất để đạt đến next_mask và kết thúc ở thành phố v. Ta lấy giá trị nhỏ nhất giữa giá trị hiện tại của dp[next_mask][v] và chi phí khi đi từ u (trong mask) đến v.
• Cuối cùng, ta tìm giá trị nhỏ nhất trong hàng cuối cùng của mảng DP (dp[(1 << N) - 1][i]) để có được chi phí nhỏ nhất khi đã thăm tất cả các thành phố.

Ví dụ 2: Bài toán Gán việc (Assignment Problem)

Bài toán: Có N công nhân và N công việc. Cho ma trận chi phí cost[i][j] là chi phí để công nhân i thực hiện công việc j. Mỗi công nhân chỉ làm một công việc và mỗi công việc chỉ được làm bởi một công nhân. Tìm cách gán việc sao cho tổng chi phí là nhỏ nhất. (N <= 20).

Phân tích: Bài toán này yêu cầu ghép cặp N công nhân với N công việc. Khi ta quyết định gán một công nhân cho một công việc, cả công nhân đó và công việc đó đều "đã được sử dụng". Trạng thái cần biết là tập hợp các công việc đã được gán (cho một số công nhân nào đó). Số lượng công nhân đã được sử dụng sẽ tương ứng với số lượng công việc đã được gán.

Định nghĩa trạng thái: dp[mask] là chi phí nhỏ nhất để gán các công việc được biểu diễn bởi mask cho k công nhân đầu tiên (công nhân 0, 1, ..., k-1), trong đó k là số bit 1 trong mask (popcount(mask)).

Kích thước mảng DP sẽ là dp[1 << N].

Trạng thái cơ sở: Không có công việc nào được gán (mask = 0), không có công nhân nào được sử dụng. Chi phí là 0. dp[0] = 0. Tất cả các trạng thái dp[mask] khác ban đầu được gán một giá trị vô cùng lớn.

Chuyển trạng thái: Duyệt qua tất cả các mask từ 0 đến (1 << N) - 1. Với mỗi mask, giả sử đã có k = popcount(mask) công việc được gán cho k công nhân đầu tiên. Công nhân tiếp theo cần được gán là công nhân thứ k. Công nhân thứ k có thể được gán cho bất kỳ công việc j nào chưa được gán trong mask. Một công việc j (từ 0 đến N-1) là chưa được gán nếu bit thứ j trong mask đang tắt: !(mask & (1 << j)). Nếu gán công nhân k cho công việc j, mask mới sẽ là mask_moi = mask | (1 << j). Chi phí sẽ tăng thêm cost[k][j]. Ta cập nhật trạng thái mới: dp[mask_moi] = min(dp[mask_moi], dp[mask] + cost[k][j]).

Kết quả cuối cùng: Sau khi duyệt hết tất cả các mask, chi phí nhỏ nhất để gán tất cả N công việc cho N công nhân đầu tiên (tức là tất cả N công nhân) sẽ là dp[(1 << N) - 1] (mask biểu diễn tập hợp tất cả N công việc).

Code minh họa (C++):

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits> // For INT_MAX or LLONG_MAX

using namespace std;

const int INF = 1e9; // Sử dụng một giá trị lớn cho vô cùng

// Hàm đếm số bit 1 trong một số nguyên (popcount)
// Có thể dùng __builtin_popcount(mask) trong GCC/Clang
int countSetBits(int n) {
    int count = 0;
    while (n > 0) {
        n &= (n - 1); // Xóa bit 1 thấp nhất
        count++;
    }
    return count;
}

int main() {
    int N; // So luong cong nhan / cong viec
    cout << "Nhap so luong cong nhan/cong viec (N <= 20): ";
    cin >> N;

    if (N > 20) {
        cout << "N qua lon, DP Bitmask khong hieu qua!" << endl;
        return 1;
    }

    vector<vector<int>> cost(N, vector<int>(N));
    cout << "Nhap ma tran chi phi cost[i][j] (cong nhan i lam cong viec j):" << endl;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> cost[i][j];
        }
    }

    // dp[mask]: chi phi nho nhat de gan cac cong viec trong mask
    // cho popcount(mask) cong nhan dau tien
    vector<int> dp(1 << N, INF);

    // Base case: Khong cong viec nao duoc gan, chi phi 0
    dp[0] = 0;

    // Duyet qua tat ca cac mask (trang thai tap cong viec da gan)
    // Tu 0 den (1 << N) - 1
    for (int mask = 0; mask < (1 << N); ++mask) {
        // Neu trang thai hien tai co the dat duoc (khac INF)
        if (dp[mask] != INF) {
            // So luong cong nhan da duoc su dung = so luong cong viec da duoc gan
            // Cong nhan tiep theo can gan la cong nhan thu 'k'
            // int k = countSetBits(mask); // hoac __builtin_popcount(mask);
            int k = 0; // Can tinh popcount cho mask
             for(int i=0; i<N; ++i) {
                 if(mask & (1 << i)) k++;
             }
            // Neu da gan het N cong viec (k == N) thi khong lam gi tiep
            if (k == N) continue;


            // Xem xet gan cong nhan thu 'k' cho mot cong viec 'j' CHUA duoc gan
            for (int j = 0; j < N; ++j) {
                // Neu cong viec 'j' CHUA co trong mask (bit thu j tat)
                if (!(mask & (1 << j))) {
                    // Mask moi sau khi gan cong viec j cho cong nhan k
                    int next_mask = mask | (1 << j);
                    // Cap nhat chi phi cho trang thai moi
                    // dp[next_mask] = min(dp[next_mask], dp[mask] + cost[k][j])
                    dp[next_mask] = min(dp[next_mask], dp[mask] + cost[k][j]);
                }
            }
        }
    }

    // Ket qua cuoi cung: chi phi nho nhat khi da gan het N cong viec
    // mask = (1 << N) - 1 (tat ca cac bit deu bat)
    int min_total_cost = dp[(1 << N) - 1];

    if (min_total_cost == INF) {
         cout << "Khong the tim duoc phuong an gan viec hop ly." << endl;
    } else {
        cout << "Chi phi nho nhat de gan viec la: " << min_total_cost << endl;
    }

    return 0;
}

Giải thích code:

• Chúng ta khởi tạo mảng dp có kích thước (1 << N) với giá trị INF. dp[mask] lưu chi phí nhỏ nhất.
• dp[0] = 0: Trạng thái cơ sở, mask 0 (binary ...0000) không có bit nào bật, biểu thị chưa có công việc nào được gán, chi phí 0.
• Hàm countSetBits(mask) (hoặc dùng __builtin_popcount(mask) nếu có) dùng để đếm số lượng bit 1 trong mask, cho biết có bao nhiêu công việc đã được gán và từ đó suy ra công nhân thứ mấy đang được xét đến.
• Vòng lặp for (int mask = 0; mask < (1 << N); ++mask): Duyệt qua tất cả các trạng thái tập hợp công việc đã gán.
• if (dp[mask] != INF): Chỉ xử lý nếu trạng thái hiện tại có thể đạt được.
• int k = ...;: Tính số lượng công việc đã được gán trong mask. Đây chính là chỉ số của công nhân tiếp theo cần được gán việc.
• Vòng lặp for (int j = 0; j < N; ++j): Xét tất cả các công việc j từ 0 đến N-1.
• if (!(mask & (1 << j))): Kiểm tra xem công việc j đã chưa được gán trong mask hiện tại hay không.
• int next_mask = mask | (1 << j);: Nếu công việc j chưa được gán, ta tạo mask mới bằng cách thêm công việc j vào tập hợp các công việc đã gán.
• dp[next_mask] = min(dp[next_mask], dp[mask] + cost[k][j]);: Cập nhật chi phí nhỏ nhất để đạt được next_mask. Chi phí này bằng chi phí để đạt được mask ban đầu cộng với chi phí khi công nhân k làm công việc j.
• Kết quả cuối cùng là dp[(1 << N) - 1], tương ứng với mask mà tất cả N bit đều bật, tức là tất cả N công việc đã được gán (cho N công nhân đầu tiên).

Khi nào nên nghĩ đến DP Bitmask?

Bạn nên xem xét kỹ thuật DP Bitmask khi bài toán của bạn có các đặc điểm sau:

1. Bài toán liên quan đến việc xử lý một tập hợp con (subset) của các đối tượng.
2. Số lượng đối tượng trong tập hợp đó nhỏ (thường <= 20).
3. Trạng thái của DP cần lưu thông tin về việc những đối tượng nào trong tập hợp đã được xử lý hoặc đã được chọn.

Bài tập ví dụ:

Cắt và Tích

Trong một ngày mưa gió, FullHouse Dev đang ngồi trong văn phòng ấm áp và được giao một bài toán thú vị về mảng số. Họ cần tìm cách cắt một mảng thành các phần và tính toán tổng của tích các phần đó.

Bài toán

Cho một mảng \(A\) gồm \(n\) phần tử. Bạn cần thực hiện đúng \(k\) lần cắt trên mảng để chia mảng thành \(k+1\) mảng con không rỗng. Sau khi mảng được chia thành các phần, bạn cần tính tích các phần tử trong mỗi phần và lấy tổng của tất cả các tích này. Vì có nhiều cách để phân chia mảng thành \(k+1\) mảng con, bạn cần in ra tổng của tất cả các cách có thể theo modulo \(10^9+7\).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(n\) - số lượng phần tử trong mảng.
• Dòng thứ hai chứa \(n\) số nguyên cách nhau bởi dấu cách - các phần tử của mảng.
• Dòng thứ ba chứa số nguyên \(k\) - số lần cắt cần thực hiện.

OUTPUT FORMAT:

• In ra một số nguyên duy nhất là tổng của tích các mảng con theo tất cả các cách cắt có thể, lấy modulo \(10^9+7\).

Ràng buộc:

• \(1 \leq n \leq 100\)
• \(1 \leq k \leq n-1\)
• \(1 \leq A[i] \leq 100\)

Ví dụ

INPUT

4
1 2 3 4
2

OUTPUT

35

Giải thích

Có 3 cách để thực hiện 2 lần cắt trong mảng đã cho:

1. 1 | 2 | 3 4

   • Tổng tích: 1 + 2 + (3 × 4) = 15

2. 1 | 2 3 | 4

   • Tổng tích: 1 + (2 × 3) + 4 = 11

3. 1 2 | 3 | 4

   • Tổng tích: (1 × 2) + 3 + 4 = 9

Tổng cuối cùng: 15 + 11 + 9 = 35 Chào bạn, đây là hướng dẫn giải bài "Cắt và Tích" bằng phương pháp Quy hoạch động (Dynamic Programming - DP) một cách ngắn gọn, tập trung vào ý tưởng và công thức.

Bài toán: Chia mảng A có n phần tử thành k+1 mảng con không rỗng bằng cách thực hiện đúng k lần cắt. Tính tổng của tích các phần tử trong mỗi mảng con, rồi cộng tổng này cho tất cả các cách cắt khác nhau. Kết quả cuối cùng lấy modulo 10^9 + 7.

Ý tưởng: Bài toán yêu cầu tính tổng trên tất cả các cấu hình chia mảng khác nhau. Điều này thường gợi ý sử dụng quy hoạch động hoặc phương pháp đếm nâng cao. Vì n nhỏ (<= 100), một giải pháp DP với độ phức tạp đa thức là khả thi.

Ta sẽ xây dựng một bảng DP để lưu trữ các kết quả trung gian. Trạng thái DP cần ghi nhớ thông tin về đoạn mảng đang xét và số lượng phần con đã tạo ra.

Định nghĩa trạng thái DP: Gọi dp[i][j] là tổng của các "tổng tích" cho tất cả các cách chia mảng con từ đoạn tiền tố A[0...i] thành đúng j phần (mảng con). Mục tiêu cuối cùng của chúng ta là tìm dp[n-1][k+1], tức là tổng của các tổng tích khi chia toàn bộ mảng A[0...n-1] thành k+1 phần.

Công thức truy hồi: Để tính dp[i][j], ta xét vị trí kết thúc của phần thứ j. Phần thứ j phải là một đoạn con liên tục kết thúc tại chỉ số i. Giả sử phần thứ j là đoạn A[p+1...i], với p là chỉ số kết thúc của phần thứ j-1. Điều kiện:

• Phần thứ j-1 phải kết thúc tại p, và các phần từ 1 đến j-1 phải chia hết đoạn A[0...p].
• Để có j phần trong A[0...i], phần thứ j-1 phải kết thúc ít nhất ở vị trí j-2 (vì mỗi phần phải không rỗng). Tức là p >= j-2.
• Phần cuối cùng A[p+1...i] phải kết thúc ở i, nên p không thể bằng i. Tức là p <= i-1. Vậy, chỉ số p chạy từ j-2 đến i-1.

Với mỗi vị trí p hợp lệ làm điểm kết thúc của phần thứ j-1:

• Đoạn A[0...p] được chia thành j-1 phần. Tổng "tổng tích" cho các cách chia này là dp[p][j-1].
• Đoạn A[p+1...i] là phần thứ j. Tích các phần tử trong đoạn này là Product(A[p+1...i]).
• Bất kỳ cách chia nào trên A[0...p] thành j-1 phần đều có thể kết hợp với phần cuối A[p+1...i].
• Tổng tích cho một cách chia cụ thể trên A[0...i] với phần cuối là A[p+1...i] sẽ là (Tổng tích của cách chia trên A[0...p] thành j-1 phần) + Product(A[p+1...i]).

Để tính dp[i][j], ta cần tính tổng của giá trị này trên tất cả các cách chia A[0...i] thành j phần mà phần thứ j là A[p+1...i], rồi cộng kết quả này cho tất cả các giá trị p hợp lệ.

Tổng trên tất cả các cách chia A[0...p] thành j-1 phần: Sum (Value_partition_A[0..p] + Product(A[p+1...i])) = Sum (Value_partition_A[0..p]) + Sum (Product(A[p+1...i])) = dp[p][j-1] + (Số cách chia A[0...p] thành j-1 phần) * Product(A[p+1...i]).

Số cách chia đoạn A[0...p] thành j-1 phần tương đương với việc đặt j-2 lần cắt vào p vị trí có thể cắt trong đoạn A[0...p] (từ sau A[0] đến sau A[p-1]). Số cách này chính là tổ hợp chập j-2 của p, ký hiệu C(p, j-2).

Vậy, công thức truy hồi là: dp[i][j] = sum_{p=j-2}^{i-1} { dp[p][j-1] + C(p, j-2) * Product(A[p+1...i]) } với điều kiện j > 1. Tất cả các phép tính cộng, nhân đều phải lấy modulo 10^9 + 7.

Trường hợp cơ sở:

• dp[i][1]: Chia A[0...i] thành 1 phần. Chỉ có 1 cách duy nhất là chính đoạn A[0...i]. Tổng tích trong trường hợp này là tích của tất cả các phần tử từ A[0] đến A[i]. dp[i][1] = Product(A[0...i]) cho i = 0, 1, ..., n-1.

Tính toán:

1. Precompute Tổ hợp C(n, k): Tính trước bảng giá trị C(i, j) sử dụng công thức Pascal C(i, j) = C(i-1, j-1) + C(i-1, j) modulo 10^9 + 7. Bảng có kích thước khoảng n x n.
2. Khởi tạo DP: Khởi tạo bảng dp kích thước n x (k+2). Các giá trị ban đầu có thể là 0.
3. Tính dp[i][1]: Duyệt i từ 0 đến n-1, tính tích lũy A[0]*...*A[i] để có dp[i][1].
4. Tính dp[i][j] cho j từ 2 đến k+1:
   • Duyệt j từ 2 đến k+1.
   • Duyệt i từ j-1 đến n-1 (để có ít nhất j phần tử cho j phần không rỗng).
   • Để tính dp[i][j], duyệt p từ j-2 đến i-1 (vị trí kết thúc của phần trước).
   • Trong vòng lặp của p, tính Product(A[p+1...i]) một cách hiệu quả bằng cách duy trì một tích chạy (running product) khi p giảm dần từ i-1 về j-2.
   • Cập nhật dp[i][j] theo công thức: dp[i][j] = (dp[i][j] + dp[p][j-1] + C(p, j-2) * Product(A[p+1...i])) % MOD. Lưu ý: dp[i][j] ban đầu là 0, nên ta chỉ cộng dồn vào.

Kết quả cuối cùng: Đáp án là dp[n-1][k+1].

Tối ưu tính Product(A[p+1...i]): Khi tính dp[i][j], ta duyệt i và j. Bên trong, ta duyệt p từ j-2 đến i-1. Thay vì tính tích A[p+1...i] lại từ đầu cho mỗi p, ta có thể duyệt p từ i-1 về j-2. Khởi tạo current_prod = A[i]. Khi p giảm đi 1, phần cuối mở rộng sang trái (bao gồm thêm A[p+1]). Tích mới sẽ là A[p+1] * current_prod.

Chi tiết vòng lặp và tối ưu:

MOD = 10^9 + 7;
// Precompute C(i, j) table up to C(n-1, n-1)
// ...

// dp table size: n x (k+2)
// Initialize dp table with 0s

// Base case j=1 (0 cuts)
current_prod = 1;
for i from 0 to n-1:
    current_prod = (current_prod * A[i]) % MOD;
    dp[i][1] = current_prod;

// Fill dp table for j > 1 (more than 0 cuts)
for j from 2 to k+1:
    for i from j-1 to n-1: // Need at least j elements for j parts
        current_prod = 1;
        // Iterate p from i-1 down to j-2
        // p is the end index of the (j-1)-th part
        // The last part is A[p+1 ... i]
        for p from i-1 down to j-2: // p >= j-2 because A[0..p] needs j-1 parts
            current_prod = (current_prod * A[p+1]) % MOD; // Calculate product A[p+1..i] iteratively

            // Add contribution: (dp[p][j-1] + C(p, j-2) * Product(A[p+1..i]))
            long long ways_to_cut_left = C[p][j-2]; // Number of ways to cut A[0..p] into j-1 parts

            long long contribution = (ways_to_cut_left * current_prod) % MOD;
            contribution = (contribution + dp[p][j-1]) % MOD;

            dp[i][j] = (dp[i][j] + contribution) % MOD;

Độ phức tạp:

• Tính C(n, k): O(n^2) thời gian, O(n^2) không gian.
• DP: 3 vòng lặp lồng nhau (j, i, p). Vòng j chạy đến k+1 (\(O(n)), vòng `i` chạy đến `n-1` (\)O(n)), vòng p chạy đến i-1 (~O(n)). Tổng thời gian O(n n n) = O(n^3).
• Không gian: O(n*(k+2)) cho DP (~O(n^2)), O(n^2) cho C. Tổng O(n^2). Với N=100, N^3 = 10^6, N^2 = 10^4. Điều này là hoàn toàn khả thi trong giới hạn thời gian và bộ nhớ.

Nhớ kiểm tra các trường hợp biên cho chỉ số p và j-2 khi tính tổ hợp C(p, j-2). C(n, k) là 0 nếu k < 0 hoặc k > n. Trong trường hợp p < j-2, C(p, j-2) sẽ là 0, nên giới hạn dưới của p là j-2 đã bao gồm trường hợp này.

Làm thêm nhiều bài tập miễn phí tại đây