I. Giới thiệu chung

1. Phát biểu bài toán

Trong các kì thi lập trình, những bài toán liên quan tới duyệt toàn bộ nghiệm không hề hiếm. Đôi khi, chúng ta sẽ gặp phải những bài toán mà bắt buộc phải duyệt toàn bộ các cấu hình nghiệm để tìm ra các nghiệm thỏa mãn yêu cầu đề bài. Cùng xét một bài toán ví dụ sau:

Cho một tập hợp $A$ gồm $n$ phần tử $a_1, a_2, \dots, a_n$. Hãy xác định có bao nhiêu tập hợp con của tập $A$ có tổng đúng bằng giá trị $s$ cho trước?

Input:

• Dòng đầu tiên chứa hai số nguyên dương $n$ và $s$.
• Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \dots, a_n$ phân tách nhau bởi dấu cách.

Ràng buộc:

• $1 \le n \le 40$.
• $1 \le s \le 10^{18}$.
• $1 \le a_i \le 10^{12}; \forall i: 1 \le i \le n$.

Output:

• Một số nguyên là số lượng tập hợp con tìm được.

Sample Input:

5 10
1 9 8 2 1

Sample Output:

4

2. Kĩ thuật Duyệt phân đôi tập hợp

Ý tưởng

Đối với những bài toán như trên, cách làm quen thuộc nhất là duyệt quay lui thử chọn ra tất cả các tập hợp khác nhau và tính tổng của chúng. Mô hình như sau (sử dụng kĩ thuật duyệt nhị phân $0 - 1$):

void backtrack(int i, int subset_sum, vector < int > &a, int s, int &res)
{
    for (int j = 0; j <= 1; ++j)
    {
        subset_sum += a[i] * j;

        if (i == n)
            res += (subset_sum == s);
        else 
            backtrack(i + 1, subset_sum a, s, res);

        subset_sum -= a[i] * j;
    }
}

Tuy nhiên, giới hạn $n$ của bài toán là $40,$ đồng nghĩa với việc thuật toán trên sẽ có độ phức tạp lên tới $O(2^{40}),$ máy tính thông thường khó có thể chạy được trong thời gian cho phép.

Kĩ thuật Duyệt phân đôi tập hợp ra đời để giải quyết những bài toán như vậy. Đây là kĩ thuật sử dụng cho các bài toán có giới hạn nhỏ, tuy nhiên lại không đủ nhỏ để áp dụng kĩ thuật duyệt toàn bộ nghiệm thông thường. Trong kĩ thuật này, chúng ta chia tập hợp ban đầu thành hai phần, duyệt sinh toàn bộ các cấu hình ở mỗi phần rồi kết hợp hai bên lại để tạo thành nghiệm của bài toán. Ý tưởng sẽ như sau:

• Bước $1$: Chia tập hợp $A$ ban đầu thành hai tập con: $a\left[1...\frac{n + 1}{2}\right]$ và $a\left[\frac{n + 1}{2} + 1...n\right]$.
• Bước $2$: Sử dụng quay lui để sinh tất cả các tổng ở mỗi tập con, lưu vào hai mảng là $\text{sum\_left}$ và $\text{sum\_right}$. Chú ý, ta sẽ lưu cả tổng $0$ (không chọn phần tử nào) để phục vụ cho quá trình xử lý tiếp theo.
• Bước $3$: Sắp xếp lại các giá trị trong mảng $\text{sum\_left}$ tăng dần.
• Bước $4$: Duyệt các tổng $s_1$ trên dãy tổng $\text{sum\_right}$. Ứng với mỗi tổng $s_1,$ ta cần xác định có bao nhiêu tổng $s_2$ trên dãy tổng $\text{sum\_left}$ thỏa mãn: $s_1 + s_2 = s$. Vì dãy tổng $\text{sum\_left}$ đã sắp xếp tăng dần, nên bước này có thể làm bằng tìm kiếm nhị phân. Ngoài ra ta đã lưu cả cách lựa chọn tập rỗng ở hai dãy, nên sẽ tính được cả những trường hợp từng giá trị của mỗi bên bằng đúng $s$.

Như vậy, độ phức tạp của giải thuật sẽ chỉ còn là $O\big(2^{\frac{n}{2}}.\log(2^{\frac{n}{2}})\big),$ hoàn toàn đáp ứng được thời gian chạy của các kì thi lập trình.

Cài đặt

#include <bits/stdc++.h>
#define int long long

using namespace std;

void enter(int &n, int &s, vector < int > &a)
{
    cin >> n >> s;

    a.resize(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
}

void generate_set(int i, int limit, int sum, vector < int > &a, vector < int > &subset_sum)
{
    for (int j = 0; j <= 1; ++j)
    {
        sum += a[i] * j;

        if (i == limit)
            subset_sum.push_back(sum);
        else
            generate_set(i + 1, limit, sum, a, subset_sum);

        sum -= a[i] * j;
    }
}

void solution(int n, int s, vector < int > &a)
{
    vector < int > sum_left, sum_right;
    generate_set(1, (n + 1) / 2, 0, a, sum_left);
    generate_set((n + 1) / 2 + 1, n, 0, a, sum_right);
    sort(sum_left.begin(), sum_left.end());

    int res = 0;
    for (int cur_s: sum_right)
    {
        if (cur_s > s)
            continue;

        auto p = equal_range(sum_left.begin(), sum_left.end(), s - cur_s);

        if (*p.first == s - cur_s)
            res += distance(p.first, p.second);
    }

    cout << res;
}

main()
{
    int n, s;
    vector < int > a;

    enter(n, s, a);
    solution(n, s, a);

    return 0;
}

II. Một số bài toán minh họa

1. Tổng vector

Đề bài

Trên mặt phẳng tọa độ $Oxy,$ cho trước $n$ vectors. Mỗi một vectors được cho bởi hai chỉ số $x$ và $y$. Ta định nghĩa vector tổng của hai vector $(x_1, y_1)$ và $(x_2, y_2)$ là vector $(x_1 + x_2, y_1 + y_2)$. Bây giờ, cần chọn ra một số vectors trong số $n$ vectors cho trước, sao cho vector tổng của chúng là vector $(u, v)$.

Yêu cầu: Biết trước vector tổng $(u, v),$ hãy đếm số cách chọn thỏa mãn yêu cầu trên?

Input:

• Dòng đầu tiên chứa số nguyên dương $n$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $x_i, y_i$ thể hiện một vector trên mặt phẳng tọa độ.
• Dòng cuối cùng chứa hai số nguyên $u, v$ - vector tổng.

Ràng buộc:

• $1 \le n \le 30$.
• $|x_i|, |y_i| \le 100; \forall i: 1 \le i \le n$.
• $|u|, |v| \le 10^9$.

Output:

• In ra một số nguyên là số lượng cách chọn thỏa mãn.

Sample Input:

4
0 0
-1 2
2 5
3 3
2 5

Sample Output:

4

Ý tưởng

Sử dụng quay lui thông thường trong bài này sẽ không thể đáp ứng thời gian chạy, vì độ phức tạp sẽ lên tới $O(2^30)$.

Ta sử dụng kĩ thuật duyệt phân đôi tập hợp để giải quyết bài toán này. Chia tập các vector ban đầu thành hai phần, duyệt quay lui để sinh ra tất cả các vector tổng trên mỗi phần. Bước này ta sẽ kết hợp thêm map để đếm số lần xuất hiện của các vector tổng trên từng phần tạo ra, lưu vào hai map là $cnt1$ và $cnt2$.

Kế đến, duyệt qua tất cả các vector tổng $(x_0, y_0)$ trên $cnt1,$ và đi tìm xem có bao nhiêu vector bằng $(u - x_0, v - y_0)$ trên $cnt2$. Bước này ta làm dễ dàng bằng map. Kết quả sẽ tăng thêm một lượng là $cnt1\big[(x_0, y_0)\big] \times cnt2\big[(u - x_0, v - y_0)\big]$.

Độ phức tạp: $O\left(2^{\frac{n}{2}}\right)$.

Cài đặt

#include <bits/stdc++.h>
#define int long long
#define task "vector_sum."

using namespace std;

void enter(int &n, vector < pair < int, int > > &vectors, int &u, int &v)
{
    cin >> n;

    vectors.resize(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> vectors[i].first >> vectors[i].second;

    cin >> u >> v;
}

void generate_set(int i, int limit, pair < int, int > vector_sum,
                  vector < pair < int, int > > &vectors,
                  map < pair < int, int >, int > &cnt)
{
    for (int j = 0; j <= 1; ++j)
    {
        vector_sum.first += vectors[i].first * j;
        vector_sum.second += vectors[i].second * j;

        if (i == limit)
            ++cnt[vector_sum];
        else
            generate_set(i + 1, limit, vector_sum, vectors, cnt);

        vector_sum.first -= vectors[i].first * j;
        vector_sum.second -= vectors[i].second * j;
    }
}

void solution(int n, vector < pair < int, int > > &vectors, int u, int v)
{
    // Duyệt sinh tất cả các vector tổng từ hai nửa tập hợp, đếm phân phối bằng map.
    map < pair < int, int >, int > cnt_left, cnt_right;
    generate_set(1, (n + 1) / 2, {0, 0}, vectors, cnt_left);
    generate_set((n + 1) / 2 + 1, n, {0, 0}, vectors, cnt_right);

    int res = 0;
    for (auto v1: cnt_right)
    {
        // Xét vector tổng tạo ra là (x, y) trên tập bên phải, thì vector 
        // cần tìm trên tập bên trái là (u - x, v - y).
        pair < int, int > v2 = {u - v1.first.first, v - v1.first.second};

        if (cnt_left.count(v2))
            res += (cnt_left[v2] * v1.second);
    }

    cout << res;
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, u, v;
    vector < pair < int, int > > vectors;

    enter(n, vectors, u, v);
    solution(n, vectors, u, v);

    return 0;
}

2. Ước số

Đề bài

Một số nguyên dương $n$ được phân tích thành thừa số nguyên tố như sau:

$$n = p_1^{k_1} \times p_2^{k_2} \times \cdots \times p_m^{k_m}$$

Yêu cầu: Cho hai số nguyên không âm $A, B \ (A \le B),$ đếm số lượng ước của $n$ thuộc đoạn $[A, B]?$

Input:

• Dòng đầu tiên chứa số nguyên dương $m$.
• Tiếp theo là $m$ dòng, dòng thứ $i$ chứa hai số nguyên dương $p_i$ và $k_i$ thể hiện phân tích nguyên tố của $n,$ trong đó các giá trị $p_i$ đôi một khác nhau.
• Ba dòng cuối cùng tương ứng với ba câu hỏi, mỗi dòng chứa hai số nguyên không âm $(A, B)$ tương ứng với một câu hỏi.

Ràng buộc:

• $1 \le m \le 25$.
• $1 \le p_i, k_i \le 10^9; \forall i: 1 \le i \le m$.
• $0 \le A \le B \le 10^9$.

Output:

• Trên ba dòng, mỗi dòng ghi một số nguyên là đáp án tương ứng với câu hỏi ở đầu vào.

Sample Input:

3
2 4
3 4
5 4
1 5
1 10
1 5 

Sample Output:

5
9
5

Ý tưởng

Đây là một bài không đơn giản, cần sử dụng kĩ thuật duyệt phân đôi tập hợp, kết hợp cùng kĩ thuật nhánh và cận. Về cơ bản, chúng ta vẫn tiến hành chia đôi tập các số nguyên tố ra và tạo tất cả các tích có thể giữa chúng, rồi ghép các tập con của hai bên lại để tạo thành các ước trong đoạn $[A, B]$.

Đối với công việc đầu tiên là sinh mọi tập con của tập các số nguyên tố ban đầu, ta sẽ có ba bước:

• Bước 1: Tạo một vector $expo[i]$: Là lũy thừa lớn nhất của số nguyên tố thứ $i$ và không vượt quá giá trị $B$ (có chứa cả giá trị $1$).
• Bước 2: Chia tập các số nguyên tố ra làm hai nửa. Áp dụng kĩ thuật duyệt phân đôi tập hợp, sinh ra mọi tập con của hai nửa đó và lưu tích của tập con vào hai tập hợp là $\text{left\_set}$ và $\text{right\_set}$. Kĩ thuật ở đây là với mỗi số nguyên tố $i,$ ta sẽ lựa chọn lần lượt các lũy thừa của nó: $p[i]^0, p[i]^1,...,p[i]^{max};$ các lũy thừa này đều đã được tính sẵn bằng vector $expo[i]$ mà bước $1$ vừa tính. Thêm một lưu ý, là mặc dù số lượng tập con có thể rất lớn, nhưng khoảng giá trị [A, B] thì chỉ là 10^9. Vì thế ta áp dụng thêm kĩ thuật nhánh cận trong quá trình sinh, nếu thấy tích hiện tại đã vượt quá B thì không cần nhân thêm các lũy thừa của các số nguyên tố sau vào nữa.
• Bước 3: Sắp xếp lại hai tập hợp lớn $\text{left\_set}$ và $\text{right\_set},$ giờ hai tập này chứa các tích sinh ra của hai nửa.

Công việc cuối cùng là ghép các giá trị của hai tập. Ứng với mỗi tích $mul$ trên tập $\text{left\_set},$ chặt nhị phân tìm đoạn vị trí $[\text{pos\_l, pos\_r}]$ trên tập $\text{right\_set}$ sao cho tích mul nhân với bất kỳ tích nào từ $\text{pos\_l}$ tới $\text{pos\_r}$ đều không bị nằm ngoài đoạn $[A, B]$. Khi đó, số lượng ước của $n$ trong đoạn $[A, B]$ sinh ra bởi $mul$ là: $(\text{pos\_r} - \text{pos\_l} + 1)$. Chúng ta cũng không cần xét riêng các tích trên từng tập hợp, vì mỗi tập hợp đều chứa một giá trị $1,$ nên sẽ xét được luôn các tập con thuộc từng tập có là ước của $n$ thuộc đoạn $[A, B]$ hay không.

Cài đặt

#include <bits/stdc++.h>
#define task "divisors."
#define inf 1e9 + 7
#define x first
#define y second

using namespace std;
const int maxm = 26;
int M;
long long product = 1;
pair < int, int > prime[maxm], q[4];
vector < long long > expo[maxm], left_set, right_set;

void enter()
{
    cin >> M;

    for (int i = 1; i <= M; ++i)
        cin >> prime[i].first >> prime[i].second;

    for (int i = 1; i <= 3; ++i)
        cin >> q[i].first >> q[i].second;
}

void create_exponentiation(int max_value)
{
    for (int i = 1; i <= M; ++i)
    {
        expo[i].push_back(1);

        for (int j = 1; j <= prime[i].second && expo[i][j - 1] * prime[i].first <= max_value; ++j)
            expo[i].push_back(expo[i][j - 1] * prime[i].first);
    }
}

void recursion(int i, int limit, int max_value, vector < long long > &current_set)
{
    if (i > limit)
        return;

    if (product * expo[i][0] > max_value)
        return;

    for (int j = 0; j < (int)expo[i].size(); ++j)
    {
        product *= expo[i][j];

        if (i == limit)
            current_set.push_back(product);
        else
            recursion(i + 1, limit, max_value, current_set);

        product /= expo[i][j];
    }
}

void solution()
{
    // Create all exponentiations p[i]^j such that p[i]^j  does not 
    // exceed the greatest value of B.
    int max_value = max(q[1].second, max(q[2].second, q[3].second));
    create_exponentiation(max_value);

    // Generate two sets of products can be formed by the prime factorization
    recursion(1, (M + 1) / 2, max_value, left_set);
    recursion((M + 1) / 2 + 1, M, max_value, right_set);
    sort(left_set.begin(), left_set.end());
    sort(right_set.begin(), right_set.end());

    // Separately handle the case that the prime factorization only 
    // consists of 1 prime.
    if (right_set.empty()) 
        right_set.push_back(1);

    // Answer the 3 queries.
    for (int i = 1; i <= 3; ++i)
    {
        int res = 0;

        // For each generated product in the left set, find the position range [pos_l, pos_r] 
        // in the right set that can be paired with it to create a product belonging to the 
        // range [A,B]. The product has a form of A <= x * y <= B.
        for (int j = 0; j < (int)left_set.size(); ++j)
        {
            int mul = left_set[j];
            if (mul > max_value)
                break;

            auto it1 = lower_bound(right_set.begin(), right_set.end(), (q[i].first + mul - 1) / mul);
            auto it2 = upper_bound(right_set.begin(), right_set.end(), q[i].second / mul) - 1;

            // If at least one position exists, get the length of the segment which can be paired.
            if (it1 != right_set.end()) 
            {
                int pos_l = it1 - right_set.begin(), pos_r = it2 - right_set.begin();
                res += (pos_r - pos_l + 1);
            }
        }

        cout << res << endl;
    }
}

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

    enter();
    solution();

    return 0;
}

III. Tài liệu tham khảo

• https://www.geeksforgeeks.org/meet-in-the-middle/
• https://www.infoarena.ro/blog/meet-in-the-middle