Để hiểu được những kiến thức được đề cập trong bài viết này, bạn đọc cần nắm vững các kiến thức liên quan tới Thao tác xử lý bit (Bit manipulation). Các bạn có thể tìm đọc bài viết về kiến thức này tại đây.

I. Mở đầu

Các phép toán thao tác bit là những phép toán rất thú vị của những ngôn ngữ lập trình được hỗ trợ riêng như C/C++ và Java. Như chúng ta đều biết, các số nguyên trong máy tính được biểu diễn bằng một chuỗi hoặc nhiều chuỗi bit (dãy nhị phân), nhờ thế, ta có thể tận dụng các số nguyên để biểu diễn những dãy bit - hay còn gọi là các bitmask. Những phép toán thao tác bit trên các bitmask là một lựa chọn hiệu quả hơn so với các CTDL như vector, set hay bitset,...nhờ vậy sẽ giúp thí sinh đạt được ưu thế trong các cuộc thi lập trình có tính cạnh tranh cao.

Một ứng dụng rất tuyệt vời của bitmask là biểu diễn các bài toán con trong các bài toán quy hoạch động. Bằng việc biểu diễn các bài toán con thông qua các dãy bit (gọi là các trạng thái) và sử dụng trạng thái nhỏ hơn để cập nhật kết quả cho các trạng thái lớn hơn, ta có một kĩ thuật rất hiệu quả để thay thế quay lui - nhánh cận, hoặc giải các bài toán quy hoạch động đếm cấu hình với số phần tử nhỏ. Trong bài viết này, tôi sẽ giới thiệu tới các bạn kĩ thuật sử dụng bitmask kết hợp với các bài toán quy hoạch động - Quy hoạch động bitmask.

II. Ý tưởng

1. Nhắc lại về "Trạng thái quy hoạch động"

Trạng thái (state) là một khái niệm cơ sở của quy hoạch động. Khi giải quyết một bài toán quy hoạch động, chúng ta cần đi tìm mục tiêu của bài toán lớn, sau đó xác định ra những bài toán con (hay những trường hợp nhỏ hơn) của bài toán lớn - đó gọi là các trạng thái.

Xét một ví dụ đơn giản:

Cho $n$ đồng xu và giá tiền của mỗi đồng $(v_0, v_1, v_2, \dots, v_{n - 1}),$ cùng với một số nguyên $s$. Tìm số đồng xu nhỏ nhất để tổng giá trị của chúng bằng $s?$ (biết rằng số lượng đồng xu không giới hạn).

Trong bài toán trên, mục tiêu là đi tìm số đồng xu nhỏ nhất sao cho tổng giá trị của chúng bằng $s$. Vậy các trạng thái sẽ là số lượng đồng xu nhỏ nhất để tổng bằng với $i$ mà $0 \le i \le s$. Muốn tìm ra trạng thái $i,$ ta phải tìm ra các trạng thái $j < i$. Và một khi đã tìm được trạng thái $i,$ ta có thể dễ dàng tìm ra trạng thái của $i + 1$.

Để lưu trữ các trạng thái, ta sẽ sử dụng mảng để lưu kết quả tính toán được mỗi bước (gọi là bảng phương án). Trong bài toán Quy hoạch động bitmask, một hoặc một số trạng thái sẽ có thể biểu diễn bởi các bitmask (thường là các dãy con, tập con), và như đã nói, bitmask cũng có thể được duyệt bằng các số nguyên. Thông qua các thao tác xử lý bit, ta có thể tìm ra các trạng thái con của một trạng thái lớn (ví dụ như $000010$ là trạng thái trước của $100010,$ tương ứng với hai số nguyên là $2$ và $34$).

2. Dấu hiệu nhận biết bài toán

Dấu hiệu đầu tiên để nhận biết những bài toán có khả năng sử dụng quy hoạch động bitmask, đó là ràng buộc dữ liệu. Thông thường, những bài toán này có độ dài của dãy số, của xâu kí tự, của tập hợp,...đều không vượt quá $20$ (có thể là những con số như $10, 15, 16,...$). Lí do là vì với ràng buộc $20,$ thì số lượng dãy con của tập hợp sinh ra sẽ là $2^{20} \approx 10^6;$ đây là ràng buộc phù hợp để sử dụng các số nguyên duyệt trạng thái, rồi kết hợp với các kĩ thuật tính toán khác mà không bị Time Limit Exceeded.

Do việc sử dụng các bitmask để biểu diễn bài toán con, nên những bài toán quy hoạch động bitmask thường liên quan tới việc lựa chọn dãy con, tập con. Bảng phương án trong dạng bài này sẽ lưu trữ kết quả của các trạng thái (biểu diễn thông qua những số nguyên), chẳng hạn như $dp[10]$ thì ta có thể ngầm hiểu là $dp[1010]$ (vì $1010_2 = 10$).

3. Phân tích ý tưởng cụ thể

Cùng xét bài toán dưới đây (ASSIGN - SPOJ) để phân tích cách lựa chọn trạng thái trong quy hoạch động bitmask:

Đề bài

Một lớp học có $n$ học sinh, cô giáo phân công cho học sinh trong lớp nghiên cứu $n$ chủ đề học tập. Mỗi học sinh có sở thích học tập khác nhau, và không có học sinh nào muốn mình phải học một chủ đề không yêu thích.

Yêu cầu: Đếm số cách phân chia $n$ chủ đề học tập cho $n$ học sinh (mỗi học sinh một chủ đề), sao cho mỗi học sinh đều được học đúng chủ đề mình yêu thích?

Input:

• Dòng đầu tiên chứa số nguyên dương $t$ - số lượng test cases.
• Trên $t$ nhóm dòng tiếp theo, mỗi nhóm dòng mô tả một test case có cấu trúc:
  • Dòng đầu tiên chứa số nguyên dương $n$.
  • Trên $n$ dòng tiếp theo, mỗi dòng chứa $n$ số nguyên $a_{i, j}$ mô tả sở thích của học sinh thứ $i$: Nếu $a_{i, j} = 0$ nghĩa là học sinh thứ $i$ không thích chủ đề $j,$ ngược lại $a_{i, j} = 1$ nghĩa là học sinh thứ $i$ yêu thích chủ đề $j$.

Ràng buộc:

• $1 \le t \le 80$.
• $1 \le n \le 20$.

Output:

• In ra số cách phân chia thỏa mãn. Đáp án đảm bảo là một số nguyên $64$ bit.

Sample Input:

3
3
1 1 1
1 1 1
1 1 1
11
1 0 0 1 0 0 0 0 0 1 1 
1 1 1 1 1 0 1 0 1 0 0 
1 0 0 1 0 0 1 1 0 1 0 
1 0 1 1 1 0 1 1 0 1 1 
0 1 1 1 0 1 0 0 1 1 1 
1 1 1 0 0 1 0 0 0 0 0 
0 0 0 0 1 0 1 0 0 0 1 
1 0 1 1 0 0 0 0 0 0 1 
0 0 1 0 1 1 0 0 0 1 1 
1 1 1 0 0 0 1 0 1 0 1 
1 0 0 0 1 1 1 1 0 0 0 
11
0 1 1 1 0 1 0 0 0 1 0 
0 0 1 1 1 1 1 1 1 1 1 
1 1 0 1 0 0 0 0 0 1 0 
0 1 0 1 0 1 0 1 0 1 1 
1 0 0 1 0 0 0 0 1 0 1 
0 0 1 0 1 1 0 0 0 0 1 
1 0 1 0 1 1 1 0 1 1 0 
1 0 1 1 0 1 1 0 0 1 0 
0 0 1 1 0 1 1 1 1 1 1 
0 1 0 0 0 0 0 0 0 1 1 
0 1 1 0 0 0 0 0 1 0 1 

Sample Output:

6
7588
7426

Ý tưởng

Ở bài toán này, mục tiêu cần đi tìm số cách phân chia $n$ chủ đề hợp lí cho $n$ học sinh. Vậy các trạng thái nhỏ hơn sẽ là số cách phân chia $i$ chủ đề hợp lý cho $i$ học sinh ($1 \le i \le n$).

Ta đánh số các học sinh và các chủ đề từ $0$ tới $n - 1$.

Sử dụng bitmask, ta sẽ biểu diễn việc một học sinh thứ $i \ (0 \le i < n)$ đã được phân chia chủ đề yêu thích của mình hay chưa. Gọi $mask$ là trạng thái thể hiện học sinh thứ $i$ đã được phân chia chủ đề hay chưa, $mask_i = 0$ tương ứng với chưa và $mask_i = 1$ tương ứng với đã phân chia rồi. Ta sẽ lần lượt tìm cách phân chia cho từng chủ đề, vậy gọi $k \ (0 \le k < n)$ là chỉ số của chủ đề đang được phân chia. Như vậy bảng phương án sẽ có dạng $dp[mask][k]$.

Ban đầu, coi như chưa có học sinh nào được phân chia chủ đề, tức là $mask = 0$ và mọi $dp[mask][k] = -1$. Xét chủ đề thứ $k$ ta cần tìm một học sinh $i$ sao cho $a_{i, k} = 1$ và bit thứ $i$ của $mask$ đang tắt, khi đó ta có thể phân chia chủ đề $k$ này cho học sinh thứ $i,$ rồi tiếp tục chuyển qua chủ đề thứ $k + 1$ và tìm học sinh để phân chia như đã làm ở bước trước. Nếu như có thể tiến tới $k = n$ tức là đã phân chia được hết $n$ chủ đề cho $n$ học sinh, thì ta sẽ có $dp[mask][k]$ được cộng thêm $1$. Như vậy, ta có công thức truy hồi:

$$dp[mask][k] = \sum dp[new\_mask][k + 1]$$

Do trạng thái nhỏ hơn sẽ cập nhật sang trạng thái lớn hơn ở mỗi bước, nên quy hoạch động top-down sẽ là một phương pháp cài đặt thuận lợi, có thể mô tả như sau:

vector < vector < long long > > dp(1 << n, vector < long long >(n, -1));

int calc(int mask, int k)
{   
    if (k == n)
        return 1;
        
    if (dp[mask][k] != -1)
        return dp[mask][k];
        
    long long ans = 0;
    for (int i = 0; i < n; ++i)
        if (a[i][k] && !(mask & (1 << i)))
            ans += calc(mask | (1 << i), k + 1);
            
    return dp[mask][k] = ans;
}

main()
{
    // Xuất phát từ trạng thái 0 - chưa có học sinh nào được phân chia chủ đề.
    // và k = 0 - chủ đề đầu tiên cần phân chia là chủ đề số 0.
    calc(0, 0);
    
    // Kết quả sẽ nằm ở dp[0][0].
    cout << dp[0][0];
    
    return 0;
}

Độ phức tạp của cách làm này là $O(n^2 \times 2^n),$ vẫn có thể gây ra tràn bộ nhớ hoặc quá thời gian chạy (do bài toán có multi-testcase), vì thế ta cần cải tiến thêm. Nhận xét rằng, nếu $mask$ hiện tại đang có $x$ bit $1$ thì tương ứng với việc đã có $x$ chủ đề được phân chia. Do ta đánh số các chủ đề từ $0,$ nên vô tình $x$ sẽ chính là số hiệu của chủ đề tiếp theo cần được phân chia.

Vậy thay vì sử dụng một chiều để lưu $k$ trong bảng phương án, ta có thể tính $k$ ở mỗi lần gọi đệ quy thông qua câu lệnh: int k = __builtin_popcount(mask), ở đây __builtin_popcount() là hàm dựng sẵn của C++ dùng để đếm số bit $1$ của một số nguyên.

Lúc này, độ phức tạp sẽ giảm xuống còn $O(2^n \times n)$.

Cài đặt

#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2")

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

using namespace std;

const int maxn = 20;
int dp[1 << maxn], a[maxn][maxn];

int calc(int n, int mask)
{
    int k = __builtin_popcount(mask);
    if (k == n)
        return 1;

    if (dp[mask] != -1)
        return dp[mask];

    int ans = 0;
    for (int i = 0; i < n; ++i)
        if (a[i][k] && !(mask & (1 << i)))
            ans += calc(n, mask | (1 << i));

    return dp[mask] = ans;
}

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

    int t;
    cin >> t;

    while (t--)
    {
        int n;
        cin >> n;

        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                cin >> a[i][j];

        // Xuất phát từ trạng thái 0 - chưa có học sinh nào được phân chia chủ đề.
        memset(dp, -1, sizeof(dp));
        calc(n, 0);

        // Kết quả sẽ nằm ở dp[0] do cách thực hiện đệ quy có nhớ.
        cout << dp[0] << '\n';
    }

    return 0;
}

Kết luận

Từ việc phân tích ví dụ trên, ta có thể rút ra một số nhận định chung về kĩ thuật Quy hoạch động bitmask như sau:

• Bảng phương án sẽ luôn luôn có một chiều $mask$ - đại diện cho trạng thái có thể biểu diễn bằng bitmask.
• Trong nhiều trường hợp, bảng phương án sẽ lưu thêm một trạng thái, trở thành dạng $dp[mask][i]$ với $i$ là vị trí cuối cùng được thêm vào tập con/dãy con. Bài toán lúc này thường sẽ có kết quả bị ảnh hưởng bởi thứ tự sắp xếp các phần tử trong một cấu hình biểu diễn bởi $mask$ - ví dụ như ở bài toán Assign bên trên. Còn nếu như kết quả của bài toán không phụ thuộc vào cách sắp xếp của các phần tử trong một cấu hình, thì thường bảng phương án chỉ có dạng $dp[mask]$ - tức là với mỗi cấu hình, cách lựa chọn đó là cố định.

Bây giờ, hãy cùng đến với một số bài tập nâng cao để hiểu rõ hơn về kĩ thuật Quy hoạch động bitmask!

III. Bài tập minh họa

1. Gói cước bạn bè

Đề bài

Một công ty có $n$ nhân viên đánh số từ $1$ tới $n$. Ông chủ công ty trang bị cho mỗi nhân viên một điện thoại di động để tiện liên lạc khi làm việc. Cước phí sử dụng điện thoại sẽ do công ty chi trả.

Sau một vài tháng hoạt động, do chi phí thanh toán các hóa đơn điện thoại khá lớn nên ông chủ quyết định tìm cách giảm chi phí bằng cách yêu cầu các nhân viên của mình đăng ký sử dụng gói cước "bạn bè" của công ty viễn thông L4T (Looking for Troubles). Gói cước "bạn bè" có đặc điểm sau:

• Mỗi gói cước chỉ cho đúng hai người đăng ký tham gia, khi hai người đăng ký sử dụng gói cước "bạn bè" thì giá cước hai người đó gọi cho nhau sẽ chỉ là $f$ đồng/phút thay vì $r$ đồng/phút theo cước phí thông thường.
• Mỗi người chỉ được tham gia không quá một gói cước "bạn bè".

Dựa vào nhu cầu công việc, ông chủ ước lượng rằng trong mỗi tháng sẽ có $m$ cuộc gọi đánh số từ $1$ tới $m,$ cuộc gọi thứ $i$ do nhân viên $u_i$ gọi nhân viên $v_i$ trong $c_i$ phút.

Yêu cầu: Hãy giúp ông chủ công ty yêu cầu các nhân viên của mình đăng ký sử dụng các gói cước “bạn bè” sao cho tổng số tiền điện thoại phải thanh toán hàng tháng cho các nhân viên là nhỏ nhất có thể?

Input:

• Dòng đầu tiên chứa hai số nguyên dương $f$ và $r$.
• Dòng thứ hai chứa một số nguyên dương chẵn $n$.
• Dòng thứ ba chứa số nguyên dương $m$.
• Trên $m$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên dương $u_i, v_i, c_i$.

Constraints:

• $1 \le f < r \le 100$.
• $2 \le n \le 16$.
• $1 \le m \le 10^4$.
• $1 \le u_i, v_i, c_i \le 100; \forall i: 1 \le i \le m$.

Output:

• Dòng đầu tin ghi số tiền phải trả hàng tháng theo phương án tìm được.
• Trên các dòng tiếp theo, mỗi dòng ghi số hiệu hai nhân viên được yêu cầu đăng ký sử dụng gói cước “bạn bè”.

Sample Input:

1 2
4
5
2 3 18
2 4 20
3 2 2
4 1 12
2 4 6

Sample Output:

84
1 4
2 3

Ý tưởng

Ta xây dựng các mảng sau:

• $val[i][j]$ có nghĩa là tổng số phút gọi của người $i$ tới người $j$.
• $all[i]$ có nghĩa là tổng số phút gọi của người $i$ tới tất cả mọi người.

Hai mảng trên có thể tính dễ dàng khi đọc vào $m$ cuộc gọi.

Gọi $f[mask]$ là số cước phí ít nhất của những người $\in mask$. Ở đây, biến $mask$ là số nguyên thể hiện trạng thái lựa chọn của $n$ nhân viên.

Ta tiến hành quy hoạch động bitmask như sau:

• Duyệt $mask$ trong đoạn $[0, 2^n-1]$.
• Với mỗi $mask,$ ta duyệt cặp $(i,j) \ (0 \le i,j < n)$. Nếu $i$ khác $j$ và cả hai bit $i, j$ đều chưa được bật trong tập $mask,$ ta tiến hành chuyển trạng thái:
  • nw = mask | (1 << i) | (1 << j) - tức là thêm người $i$ và $j$ vào tập bằng cách bật bit ở vị trí $i$ và $j$ lên.
  • Cập nhật: $cost = 2 \times val[i][j] \times F + (all[i]-val[i][j]) \times R + (all[j] - val[j][i]) \times R;$ với $cost$ là chi phí của người $i$ và $j$ gọi tới các người khác. Do ta ghép cặp người $i$ với người $j,$ chi phí các cuộc gọi giữa họ chính là $F,$ còn chi phí của họ gọi tới các người khác chính là $R$.
  • Để truy vết, ta sử dụng một mảng kiểu pair < int, int > là $tv[2^n]$ - với $tv[mask]$ là để truy vết $f[mask]$ được cập nhật tối ưu nhờ thêm hai người nào.
  • Nếu $f[nw] > f[mask] + cost,$ ta có:
    • $f[nw] = f[mask] + cost$.
    • $tv[nw] = (i, j)$.

Đáp án của bài toán chính là $\frac{f[2^n-1]}{2},$ bởi đoạn $cost$ khi cập nhật ta đã tính trùng $2$ lần.

Để truy vết kết quả, ta sẽ dùng mảng $tv$ đi ngược lại như sau:

int mask = mx - 1;
while (mask) 
{
    pair < int, int > t = tv[mask];
    cout << t.first + 1 << ' ' << t.second + 1 << '\n';

    // Mỗi bước truy vết thì tắt 2 bit đã bật trong bước hiện tại.
    mask ^= (1 << t.first);
    mask ^= (1 << t.second);
}

Độ phức tạp: $O(2^n \times n^2)$.

Code mẫu

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

using namespace std;

const int maxn = 16;
int f, r, n, m;
int val[maxn][maxn], all[maxn];
int dp[1 << maxn];
pair < int, int > tv[1 << maxn];

bool mini(int &a, int b) 
{
    if (a > b) 
    {
        a = b;
        return true;
    }

    return false;
}

void solution()
{
    memset(dp, 0x3f3f3f, sizeof(dp));
    int inf = dp[0];
    dp[0] = 0;
    int mx = 1 << n;
    for (int mask = 0; mask < mx; ++mask) 
    {
        if (dp[mask] == inf) 
            continue;

        for (int i = 0; i < n; ++i) 
        {
            if (mask & (1 << i)) 
                continue;

            for (int j = 0; j < n; ++j) 
            {
                if (i == j || (mask & (1 << j))) 
                    continue;

                int nw = mask | (1 << i) | (1 << j);
                if (mini(dp[nw], dp[mask] + 2 * val[i][j] * f + (all[i] - val[i][j]) * r + (all[j] - val[j][i]) * r)) 
                    tv[nw] = {i,j};
            }
        }
    }

    cout << dp[mx - 1] / 2 << '\n';

    // Truy vết.
    int mask = mx - 1;
    while (mask) 
    {
        pair < int, int > t = tv[mask];
        cout << t.first + 1 << ' ' << t.second + 1 << '\n';
        mask ^= (1 << t.first);
        mask ^= (1 << t.second);
    }
}

main() 
{
    cin >> f >> r >> n >> m;

    for (int i = 1; i <= m; i++) 
    {
        int u,v,c; 
        cin >> u >> v >> c; 
        
        u--; 
        v--;
        if (u > v) 
            swap(u,v);

        val[u][v] += c;
        val[v][u] += c;
        all[u] += c;
        all[v] += c;
    }

    solution();

    return 0;
}

2. Phép tính cổ

Đề bài

Một đoàn khảo cổ đang thám hiểm một hang động, và tình cờ tìm thấy một căn hầm từ thời cổ đại. Điều đặc biệt là căn hầm này mặc dù đã có từ xa xưa, nhưng lại có hệ thống mật mã giống như các hệ thống hiện đại. Trên cửa hầm có ghi một bài toán cổ, đáp án của bài toán đó chính là mật mã để vào trong căn hầm. Bài toán như sau:

Cho trước hai số nguyên dương $n$ và $m$. Mật mã của căn hầm là số lượng số $x$ gần với $n \text{ mod } m$. Biết rằng, một số nguyên dương $x$ được gọi là gần với $n \text{ mod } m$ nếu như nó thỏa mãn các điều sau:

• $x$ được tạo thành bằng cách hoán vị các chữ số của $n$.
• $x$ không bắt đầu bằng chữ số $0$.
• $x$ chia hết cho $m$.

Yêu cầu: Hãy giúp đoàn khảo cổ tìm ra mật mã của căn hầm?

Input:

• Một dòng duy nhất chứa hai số nguyên dương $n$ và $m$ phân tách nhau bởi dấu cách.

Ràng buộc:

• $1 \le n \le 10^{18}$.
• $1 \le m \le 100$.

Subtasks:

• Subtask $1$ ($40\%$ số điểm): $1 \le n \le 10^9$.
• Subtask $2$ ($60\%$ số điểm): Không có ràng buộc gì thêm.

Output:

• Số nguyên duy nhất là mật mã tìm được.

Sample Input 1:

104 2

Sample Output 1:

3

Sample Input 2:

223 4

Sample Output 2:

1

Sample Input 3:

7067678 8

Sample Output 3:

47

Ý tưởng

Subtask 1

Với subtask này, vì $n \le 10^9$ nên ta có thể sử dụng quay lui để sinh mọi hoán vị của $n$ và đếm số hoán vị chia hết cho $m$. Tuy nhiên, cần lưu ý các trường hợp hoán vị sinh ra bị trùng nhau, cũng như các hoán vị bắt đầu bằng chữ số $0$ thì không đếm.

Độ phức tạp: $O\left(|n|!\right),$ với $|n|$ là số chữ số của $n$.

Subtask 2

Với subtask này, ta sử dụng quy hoạch động trạng thái.

Đặt $dp[mask][r]$ là số hoán vị của $n$ với các chữ số được chọn theo trạng thái $mask,$ và chia cho $m$ dư $r$.

Giả sử trạng thái hiện tại là $mask,$ và chúng ta muốn thêm chữ số ở vị trí thứ $i \ \big(0 \le i < |n|\big)$ vào trạng thái này (đồng nghĩa với việc phải bật bit thứ $i$ trong $mask$ lên). Ta sẽ cập nhật từ trạng thái $dp[mask][i]$ lên trạng thái tiếp theo dựa trên hai yếu tố:

• Trạng thái mới là: $mask \text{ or } 2^i$.
• Thêm chữ số thứ $i$ vào vị trí cuối cùng của các số được tạo ra bởi trạng thái $mask$ mà chia cho $m$ dư $r;$ từ đó tạo ra số mới có số dư khi chia cho $m$ là: $\big(r \times 10 + n_i\big) \text{ mod } m$.

Từ đây rút ra công thức:

$$dp\big[mask \text{ or } 2^i\big]\big[(r \times 10 + n_i) \text{ mod } m\big] = dp\big[mask \text{ or } 2^i\big]\big[(r \times 10 + n_i) \text{ mod } m\big] + dp\big[mask\big]\big[r\big]$$

Tuy nhiên, có một vấn đề xảy ra là đối với những chữ số giống nhau ở trong $n,$ thì việc hoán vị chúng sẽ tạo ra các số giống nhau. Lấy ví dụ, nếu có $3$ chữ số được chọn cùng là chữ số $1,$ thì những hoán vị được tạo ra mà có chứa ba chữ số này sẽ bị lặp lại tới $3! = 6$ lần. Vì thế, ta cần phải loại bỏ những trường hợp trùng lặp này. Có $2$ cách để làm điều đó:

• Cách $1$: Sau khi tính toán xong toàn bộ mảng $dp,$ chia kết quả cuối cùng cho các giá trị $cnt[d]!,$ với $d$ là các chữ số trong $n$ và $cnt[d]$ là số lần xuất hiện của chúng.
• Cách $2$: Sử dụng một mảng đánh dấu trong quá trình tính toán là $visited[d]$ để thể hiện rằng chữ số $d$ đã được chọn hay chưa. Nếu đã chọn rồi thì không cập nhật trạng thái hiện tại lên kết quả nữa.

Độ phức tạp: $O\big(2^{|n|} \times |n| \times m\big)$.

Code mẫu

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int maxn = (1 << 18) + 5, maxr = 105;
int m;
int dp[maxn][maxr], visited[20];
string n;
 
void enter()
{
    cin >> n >> m;
}
 
void solution()
{
    dp[0][0] = 1;
 
    for (int mask = 0; mask < (1 << n.size()); ++mask)
        for (int r = 0; r < m; ++r)
        {
            memset(visited, 0, sizeof(visited));
 
            for (int i = 0; i < n.size(); ++i)
            {
                int digit = n[i] - '0';
 
                if (mask & (1 << i)) // If digit is was chosen, then consider next digit.
                    continue;
                if (mask == 0 && digit == 0) // Do not choose the first digit is zero.
                    continue;
                if (visited[digit])
                    continue;
 
                visited[digit] = 1;
                dp[mask | (1 << i)][(r * 10 + digit) % m] += dp[mask][r];
            }
        }
 
    cout << dp[(1 << n.size()) - 1][0];
}
 
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    enter();
    solution();
 
    return 0;
}

Các bạn có thể luyện tập thêm về các bài tập quy hoạch động bitmask tại một số nguồn dưới đây:

• VNOI DP Bitmask 1.
• VNOI DP Bitmask 2.

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

• https://vnoi.info/wiki/translate/topcoder/dynamic-programming.md
• https://www.hackerearth.com/practice/algorithms/dynamic-programming/bit-masking/tutorial/?fbclid=IwAR2RG8fGRbrn7FH2Ri_MAijUoFN7XCvQjBnskUMsFunlN69CeXDA3zRdcAw
• https://www.geeksforgeeks.org/bitmasking-and-dynamic-programming-set-1-count-ways-to-assign-unique-cap-to-every-person/
• https://cp.cyberlabs.club/docs/roadmap/advanced/dp-with-bitmasks/

---

©️ Tác giả: Vũ Quế Lâm từ Viblo