+5

Quy hoạch động Bitmask

Để 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 nn đồng xu và giá tiền của mỗi đồng (v0,v1,v2,,vn1),(v_0, v_1, v_2, \dots, v_{n - 1}), cùng với một số nguyên ss. Tìm số đồng xu nhỏ nhất để tổng giá trị của chúng bằng s?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 ss. Vậy các trạng thái sẽ là số lượng đồng xu nhỏ nhất để tổng bằng với ii0is0 \le i \le s. Muốn tìm ra trạng thái i,i, ta phải tìm ra các trạng thái j<ij < i. Và một khi đã tìm được trạng thái i,i, ta có thể dễ dàng tìm ra trạng thái của i+1i + 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ư 000010000010 là trạng thái trước của 100010,100010, tương ứng với hai số nguyên là 223434).

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á 2020 (có thể là những con số như 10,15,16,...10, 15, 16,...). Lí do là vì với ràng buộc 20,20, thì số lượng dãy con của tập hợp sinh ra sẽ là 220106;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]dp[10] thì ta có thể ngầm hiểu là dp[1010]dp[1010] (vì 10102=101010_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ó nn học sinh, cô giáo phân công cho học sinh trong lớp nghiên cứu nn 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 nn chủ đề học tập cho nn 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 tt - số lượng test cases.
  • Trên tt 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 nn.
    • Trên nn dòng tiếp theo, mỗi dòng chứa nn số nguyên ai,ja_{i, j} mô tả sở thích của học sinh thứ ii: Nếu ai,j=0a_{i, j} = 0 nghĩa là học sinh thứ ii không thích chủ đề j,j, ngược lại ai,j=1a_{i, j} = 1 nghĩa là học sinh thứ ii yêu thích chủ đề jj.

Ràng buộc:

  • 1t801 \le t \le 80.
  • 1n201 \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 6464 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 nn chủ đề hợp lí cho nn học sinh. Vậy các trạng thái nhỏ hơn sẽ là số cách phân chia ii chủ đề hợp lý cho ii học sinh (1in1 \le i \le n).

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

Sử dụng bitmask, ta sẽ biểu diễn việc một học sinh thứ i (0i<n)i \ (0 \le i < n) đã được phân chia chủ đề yêu thích của mình hay chưa. Gọi maskmask là trạng thái thể hiện học sinh thứ ii đã được phân chia chủ đề hay chưa, maski=0mask_i = 0 tương ứng với chưa và maski=1mask_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 (0k<n)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]dp[mask][k].

Ban đầu, coi như chưa có học sinh nào được phân chia chủ đề, tức là mask=0mask = 0 và mọi dp[mask][k]=1dp[mask][k] = -1. Xét chủ đề thứ kk ta cần tìm một học sinh ii sao cho ai,k=1a_{i, k} = 1 và bit thứ ii của maskmask đang tắt, khi đó ta có thể phân chia chủ đề kk này cho học sinh thứ i,i, rồi tiếp tục chuyển qua chủ đề thứ k+1k + 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=nk = n tức là đã phân chia được hết nn chủ đề cho nn học sinh, thì ta sẽ có dp[mask][k]dp[mask][k] được cộng thêm 11. Như vậy, ta có công thức truy hồi:

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

với new_masknew\_mask là giá trị maskmask sau khi đã bật bit ở vị trí thứ ii lên và maski=0mask_i = 0

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(n2×2n),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 maskmask hiện tại đang có xx bit 11 thì tương ứng với việc đã có xx chủ đề được phân chia. Do ta đánh số các chủ đề từ 0,0, nên vô tình xx 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 kk trong bảng phương án, ta có thể tính kk ở 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 11 của một số nguyên.

Lúc này, độ phức tạp sẽ giảm xuống còn O(2n×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 maskmask - đạ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]dp[mask][i] với ii 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 maskmask - 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]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ó nn nhân viên đánh số từ 11 tới nn. Ô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à ff đồng/phút thay vì rr đồ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ó mm cuộc gọi đánh số từ 11 tới m,m, cuộc gọi thứ ii do nhân viên uiu_i gọi nhân viên viv_i trong cic_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 ffrr.
  • Dòng thứ hai chứa một số nguyên dương chẵn nn.
  • Dòng thứ ba chứa số nguyên dương mm.
  • Trên mm dòng tiếp theo, dòng thứ ii chứa ba số nguyên dương ui,vi,ciu_i, v_i, c_i.

Constraints:

  • 1f<r1001 \le f < r \le 100.
  • 2n162 \le n \le 16.
  • 1m1041 \le m \le 10^4.
  • 1ui,vi,ci100;i:1im1 \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]val[i][j] có nghĩa là tổng số phút gọi của người ii tới người jj.
  • all[i]all[i] có nghĩa là tổng số phút gọi của người ii 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 mm cuộc gọi.

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

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

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

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

Để truy vết kết quả, ta sẽ dùng mảng tvtv đ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(2n×n2)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 nn và mm. Mật mã của căn hầm là số lượng số xx gần với n mod mn \text{ mod } m. Biết rằng, một số nguyên dương xx được gọi là gần với n mod mn \text{ mod } m nếu như nó thỏa mãn các điều sau:

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

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 nn và mm phân tách nhau bởi dấu cách.

Ràng buộc:

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

Subtasks:

  • Subtask 11 (40%40\% số điểm): 1n1091 \le n \le 10^9.
  • Subtask 22 (60%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ì n109n \le 10^9 nên ta có thể sử dụng quay lui để sinh mọi hoán vị của nn và đếm số hoán vị chia hết cho mm. 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ố 00 thì không đếm.

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

Subtask 2

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

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

Giả sử trạng thái hiện tại là mask,mask, và chúng ta muốn thêm chữ số ở vị trí thứ i (0i<n)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ứ ii trong maskmask lên). Ta sẽ cập nhật từ trạng thái dp[mask][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 or 2imask \text{ or } 2^i.
  • Thêm chữ số thứ ii vào vị trí cuối cùng của các số được tạo ra bởi trạng thái maskmask mà chia cho mmr;r; từ đó tạo ra số mới có số dư khi chia cho mm là: (r×10+ni) mod m\big(r \times 10 + n_i\big) \text{ mod } m.

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

dp[mask or 2i][(r×10+ni) mod m]=dp[mask or 2i][(r×10+ni) mod m]+dp[mask][r]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]

với or\text{or} là toán tử | xử lý bit

Tuy nhiên, có một vấn đề xảy ra là đối với những chữ số giống nhau ở trong n,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ó 33 chữ số được chọn cùng là chữ số 1,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!=63! = 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ó 22 cách để làm điều đó:

  • Cách 11: Sau khi tính toán xong toàn bộ mảng dp,dp, chia kết quả cuối cùng cho các giá trị cnt[d]!,cnt[d]!, với dd là các chữ số trong nn và cnt[d]cnt[d] là số lần xuất hiện của chúng.
  • Cách 22: Sử dụng một mảng đánh dấu trong quá trình tính toán là visited[d]visited[d] để thể hiện rằng chữ số dd đã đượ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(2n×n×m)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:

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


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


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.