Hướng giải của Chia Quà Cho Nhiều Lớp

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Lời giải: Chia \(N\) phần quà thành \(K\) nhóm có tổng bằng nhau

Ý tưởng tổng quát

Đặt \(T\) là tổng khối lượng tất cả. Nếu \(T\) không chia hết cho \(K\), đáp án là \(0\).

Ngược lại, đặt target = T / K. Ta cần đếm số cách phân hoạch \(\{1,\ldots,N\}\) thành đúng \(K\) nhóm đôi một rời nhau, mỗi nhóm có tổng bằng target (các nhóm không gán nhãn – hai cách phân hoạch chỉ khác nhau khi tồn tại một nhóm khác).

Thuật giải đệ quy kèm phá vỡ đối xứng

Tính trước sum[mask] cho mọi mask (kỹ thuật tách bit thấp nhất): sum[mask] = sum[mask ^ lsb] + a[ctz(lsb)].

Ta đệ quy dfs(mask, groupsLeft):

  • Nếu groupsLeft == 0 và mask == 0: đếm \(1\).
  • Ngược lại, nếu mask == 0: bỏ qua.
  • Lấy i là chỉ số nhỏ nhất còn lại trong mask (đảm bảo nhóm đầu tiên luôn chứa phần tử nhỏ nhất, tránh đếm các cách phân hoạch chỉ khác nhau bởi thứ tự nhóm).
  • Duyệt sub là con của mask \ (1<<i), ghép (1<<i) | sub để được nhóm đầu tiên; chỉ tiếp tục nếu tổng đúng bằng target.

Cách làm này đếm các phân hoạch không thứ tự và bỏ sót rất ít.

Đánh giá độ phức tạp

  • Tính sum[mask]: \(O(N \cdot 2^N)\).
  • Đệ quy: tùy thuộc vào số "good" submask, trong giới hạn \(N \le 20\), \(K \le 6\) hoàn toàn nhanh.

Mã nguồn tham khảo

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, K;
    if (!(cin >> n >> K)) return 0;
    vector<int> a(n);
    long long total = 0;
    for (int i = 0; i < n; i++) { cin >> a[i]; total += a[i]; }

    if (total % K != 0) { cout << 0 << "\n"; return 0; }
    int target = (int)(total / K);

    int full = 1 << n;
    vector<int> sumMask(full, 0);
    for (int m = 1; m < full; m++) {
        int lsb = m & -m;
        sumMask[m] = sumMask[m ^ lsb] + a[__builtin_ctz(lsb)];
    }

    long long count = 0;
    function<void(int,int)> dfs = [&](int mask, int groupsLeft) {
        if (groupsLeft == 0) {
            if (mask == 0) count++;
            return;
        }
        if (mask == 0) return;
        int smallest = __builtin_ctz(mask);
        int rest = mask ^ (1 << smallest);
        int sub = rest;
        while (true) {
            int S = sub | (1 << smallest);
            if (sumMask[S] == target) {
                dfs(mask ^ S, groupsLeft - 1);
            }
            if (sub == 0) break;
            sub = (sub - 1) & rest;
        }
    };

    dfs(full - 1, K);
    cout << count << "\n";
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.