Nguyên Lý Bao Hàm - Loại Trừ (Inclusion-Exclusion) Trong Lập Trình Thi Đấu
Trong các bài toán đếm nâng cao của các kỳ thi Học sinh giỏi Quốc gia (VOI) và thi đấu quốc tế, chúng ta thường xuyên đối mặt với bài toán đếm số lượng phần tử thỏa mãn ít nhất một trong số các điều kiện cho trước. Việc đếm trực tiếp từng điều kiện sẽ dẫn đến sai lầm đếm trùng các phần tử thỏa mãn đồng thời nhiều điều kiện, trong khi việc kiểm tra từng phần tử bằng vòng lặp vét cạn là bất khả thi khi kích thước không gian tìm kiếm lên tới \(10^9\) hay \(10^{18}\).
Nguyên lý Bao hàm - Loại trừ (The Inclusion-Exclusion Principle), hay thường được gọi thân thuộc là nguyên lý bù trừ, là một vũ khí toán học mạnh mẽ giúp giải quyết bài toán này một cách chính xác. Bằng cách cộng kích thước của từng điều kiện đơn lẻ, trừ đi phần giao của từng cặp điều kiện, cộng lại phần giao của từng bộ ba điều kiện, và xen kẽ dấu liên tục cho đến khi xét hết mọi tập con, ta thu được kết quả chính xác tuyệt đối.
Bài viết này sẽ đi sâu vào cấu trúc toán học của nguyên lý bù trừ, biểu diễn trực quan qua sơ đồ Venn, và hướng dẫn chi tiết cách cài đặt bằng kỹ thuật duyệt trạng thái Bitmask (mặt nạ bit) đạt hiệu năng tối đa.
1. Công thức toán học tổng quát và sơ đồ Venn
Trường hợp 2 và 3 tập hợp
Xét hai tập hợp hữu hạn \(A\) và \(B\). Số phần tử thuộc hợp của hai tập hợp được tính bằng: \[|A \cup B| = |A| + |B| - |A \cap B|\]
Xét ba tập hợp \(A, B, C\), công thức mở rộng thành: \[|A \cup B \cup C| = (|A| + |B| + |C|) - (|A \cap B| + |B \cap C| + |C \cap A|) + (|A \cap B \cap C|)\]
Công thức tổng quát cho K tập hợp
Cho \(K\) tập hợp hữu hạn \(A_1, A_2, \dots, A_K\). Số lượng phần tử thuộc ít nhất một tập hợp là:
\[|\bigcup_{i=1}^K A_i| = \sum_{\emptyset \ne S \subseteq \{1, \dots, K\}} (-1)^{|S| - 1} |\bigcap_{i \in S} A_i|\]
Quy tắc nhớ dấu bất biến:
- Tập con \(S\) có số lượng phần tử lẻ (\(|S| = 1, 3, 5, \dots\)): Mang dấu CỘNG (+).
- Tập con \(S\) có số lượng phần tử chẵn (\(|S| = 2, 4, 6, \dots\)): Mang dấu TRỪ (-).
2. Kỹ thuật cài đặt bằng duyệt Bitmask (Mặt nạ bit)
Khi áp dụng nguyên lý bù trừ trong lập trình, số lượng tập hợp \(K\) thường nhỏ (\(K \le 15\) hoặc \(K \le 20\)). Để xét toàn bộ \(2^K - 1\) tập con khác rỗng của \(K\) phần tử, công cụ tự nhiên và nhanh nhất chính là biểu diễn nhị phân thông qua một số nguyên mask chạy từ \(1\) đến \(2^K - 1\).
Mỗi bit thứ \(i\) của mask (\(0 \le i < K\)) được hiểu như sau:
- Nếu bit thứ \(i\) bật (\(mask \& (1 \ll i) \ne 0\)): Điều kiện thứ \(i\) được chọn vào tập con \(S\).
- Nếu bit thứ \(i\) tắt: Bỏ qua điều kiện thứ \(i\).
Số lượng bit bật của mask chính là kích thước \(|S|\), có thể tính nhanh bằng hàm nội trang __builtin_popcount(mask) trong GCC C++ hoặc phương thức int.bit_count() trong Python.
Ví dụ kinh điển: Đếm số chia hết cho ít nhất một số nguyên tố
Đề bài: Cho số nguyên dương \(N\) (\(N \le 10^{18}\)) và một tập hợp gồm \(K\) số nguyên tố \(P = \{p_1, p_2, \dots, p_K\}\) với \(K \le 15\). Hãy đếm xem có bao nhiêu số nguyên trong đoạn \([1, N]\) chia hết cho ít nhất một số nguyên tố trong tập \(P\).
Phân tích:
- Gọi \(A_i\) là tập các số trong \([1, N]\) chia hết cho \(p_i\). Kích thước \(|A_i| = \lfloor N / p_i \rfloor\).
- Phần giao của một tập con các số nguyên tố \(S\) chính là số các số chia hết cho tích của chúng: \[|\bigcap_{i \in S} A_i| = \left\lfloor \frac{N}{\prod_{i \in S} p_i} \right\rfloor\]
- Áp dụng nguyên lý bù trừ, ta chỉ cần duyệt qua mọi
mask, tính tích các phần tử được bật, kiểm tra tràn số, rồi cộng hoặc trừ \(\lfloor N / \text{tích} \rfloor\) vào đáp số tùy theo tính chẵn lẻ của số lượng bit.
Chủ đề này nằm trong Buổi 11 - Inclusion-Exclusion, Catalan & Probability của Tài năng lập trình. Xem đề cương
3. Cài đặt chuẩn C++17 và Python 3
Dưới đây là mã nguồn chuẩn giải quyết bài toán trên:
Cài đặt C++17
#include <iostream>
#include <vector>
using namespace std;
// Dem so nguyen trong [1, n] chia het cho it nhat 1 so trong tap primes
long long count_divisible(long long n, const vector<long long>& primes) {
int k = primes.size();
long long ans = 0;
// Duyet moi tap con khac rong bang bitmask tu 1 den (1 << k) - 1
for (int mask = 1; mask < (1 << k); ++mask) {
long long prod = 1;
int bits = 0;
bool overflow = false;
for (int i = 0; i < k; ++i) {
if (mask & (1 << i)) {
bits++;
// Kiem tra tran so tich prod * primes[i] vuot qua n
if (prod > n / primes[i]) {
overflow = true;
break;
}
prod *= primes[i];
}
}
if (overflow) continue;
long long count = n / prod;
if (bits % 2 == 1) {
ans += count; // Tap le: Cong
} else {
ans -= count; // Tap chan: Tru
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n = 100;
vector<long long> primes = {2, 3, 5};
// Ket qua: 74 so trong [1, 100] chia het cho 2, 3 hoac 5
cout << count_divisible(n, primes) << '\n';
return 0;
}
Cài đặt Python 3
import sys
def count_divisible(n: int, primes: list[int]) -> int:
k = len(primes)
ans = 0
# Duyet 2^k - 1 trang thai bitmask
for mask in range(1, 1 << k):
prod = 1
bits = 0
overflow = False
for i in range(k):
if mask & (1 << i):
bits += 1
prod *= primes[i]
if prod > n:
overflow = True
break
if overflow:
continue
cnt = n // prod
if bits % 2 == 1:
ans += cnt
else:
ans -= cnt
return ans
def main():
n = 100
primes = [2, 3, 5]
print(count_divisible(n, primes))
if __name__ == '__main__':
main()
4. Các biến thể bài toán ứng dụng nguyên lý bù trừ
-
Đếm số lượng số nguyên tố cùng nhau với \(M\) trong đoạn \([1, N]\):
- Phân tích \(M\) thành các thừa số nguyên tố phân biệt: \(M = p_1^{a_1} \cdot p_2^{a_2} \dots p_k^{a_k}\).
- Số các số trong \([1, N]\) nguyên tố cùng nhau với \(M\) chính là: \[\text{Ans} = N - (\text{số các số chia hết cho ít nhất một } p_i)\]
- Áp dụng nguyên lý bù trừ trên tập thừa số nguyên tố \(\{p_1, \dots, p_k\}\) giúp giải bài toán trong thời gian \(O(2^k)\), với \(k \le 15\) cho mọi \(M \le 10^{18}\) (vì tích 15 số nguyên tố đầu tiên \(2 \cdot 3 \cdot 5 \cdots 47 \approx 6.1 \times 10^{17}\), còn tích 16 số đầu đã vượt \(10^{18}\)).
-
Bài toán số hoán vị không có điểm cố định (Derangements):
- Đếm số cách xếp \(N\) lá thư vào \(N\) phong bì sao cho không lá thư nào nằm đúng phong bì của nó.
- Bằng nguyên lý bù trừ trên các tính chất "lá thư thứ \(i\) nằm đúng vị trí", ta tìm ra công thức đóng nổi tiếng: \[D_n = n! \sum_{i=0}^n \frac{(-1)^i}{i!} = \left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor \quad (n \ge 1)\]
-
Đếm số đường đi tránh tập các ô cản trên lưới:
- Khi lưới có kích thước rất lớn (\(10^5 \times 10^5\)) nhưng số lượng ô cản \(K\) rất nhỏ (\(K \le 2000\)), ta quy hoạch động sắp xếp các ô cản theo tọa độ và áp dụng bù trừ: \[\text{Đường đi hợp lệ} = \text{Tổng mọi đường} - \text{Số đường đi qua ít nhất một ô cản}\]
Bảng chạy tay chi tiết từng bước thuật toán bù trừ
Xét bài toán đếm số lượng số nguyên trong đoạn \([1, 100]\) chia hết cho ít nhất một trong ba số nguyên tố \(\{2, 3, 5\}\). Có \(K = 3\) số nguyên tố, tổng cộng có \(2^3 - 1 = 7\) trạng thái tập con khác rỗng được duyệt qua biểu diễn nhị phân của mask từ 1 đến 7:
| Mask (Nhị phân) | Tập số nguyên tố chọn | Tích (prod) | Số bit bật (bits) | Số lượng: 100 / prod | Dấu đóng góp | Giá trị đóng góp |
|---|---|---|---|---|---|---|
1 (001) |
\(\{2\}\) | 2 | 1 (Lẻ) | \(\lfloor 100 / 2 \rfloor = 50\) | \(+\) | \(+50\) |
2 (010) |
\(\{3\}\) | 3 | 1 (Lẻ) | \(\lfloor 100 / 3 \rfloor = 33\) | \(+\) | \(+33\) |
3 (011) |
\(\{2, 3\}\) | 6 | 2 (Chẵn) | \(\lfloor 100 / 6 \rfloor = 16\) | \(-\) | \(-16\) |
4 (100) |
\(\{5\}\) | 5 | 1 (Lẻ) | \(\lfloor 100 / 5 \rfloor = 20\) | \(+\) | \(+20\) |
5 (101) |
\(\{2, 5\}\) | 10 | 2 (Chẵn) | \(\lfloor 100 / 10 \rfloor = 10\) | \(-\) | \(-10\) |
6 (110) |
\(\{3, 5\}\) | 15 | 2 (Chẵn) | \(\lfloor 100 / 15 \rfloor = 6\) | \(-\) | \(-6\) |
7 (111) |
\(\{2, 3, 5\}\) | 30 | 3 (Lẻ) | \(\lfloor 100 / 30 \rfloor = 3\) | \(+\) | \(+3\) |
Tổng hợp lại kết quả: \[\text{Tổng} = (50 + 33 + 20) - (16 + 10 + 6) + 3 = 103 - 32 + 3 = 74\]
Kết quả 74 số hoàn toàn khớp với đếm vét cạn thực tế. Bảng chạy tay này giúp người lập trình hình dung trực quan cơ chế đảo dấu luân phiên của nguyên lý bù trừ.
Bốn cạm bẫy thường gặp khi cài đặt nguyên lý bù trừ
Khi áp dụng nguyên lý bù trừ trong các kỳ thi học sinh giỏi và lập trình thi đấu, có 4 sai lầm phổ biến mà bạn cần đặc biệt lưu tâm:
-
Tràn số khi nhân tích các phần tử được chọn: Khi số tập hợp \(K \approx 20\), tích của các số nguyên tố có thể dễ dàng vượt quá giới hạn \(2^{63} - 1\) của kiểu
long long. Thay vì nhân trực tiếpprod *= prồi mới so sánh với \(N\), bạn phải luôn kiểm tra an toàn trước:if (prod > n / p) { overflow = true; break; }. Việc chia trước giúp ngăn chặn triệt để hành vi tràn số không xác định (Undefined Behavior). -
Quy ước dấu chẵn lẻ bị ngược: Công thức bù trừ quy định: tập hợp con có số lượng phần tử lẻ mang dấu DƯƠNG (\(+\)), còn tập hợp có số lượng phần tử chẵn mang dấu ÂM (\(-\)). Nhiều thí sinh nhầm lẫn giữa tính chẵn lẻ của mask với tính chẵn lẻ của số lượng bit
__builtin_popcount(mask), dẫn đến kết quả bị sai dấu toàn bộ. -
Bắt đầu vòng lặp bitmask từ 0: Trạng thái
mask = 0đại diện cho tập hợp rỗng, không chứa phần tử nào. Nếu duyệt từ 0, phép tính tích hoặc kiểm tra điều kiện sẽ gặp lỗi chia cho 0 hoặc làm sai lệch kết quả cuối cùng. Luôn khởi tạomask = 1và chạy tới(1 << k) - 1. -
Kích thước tập hợp \(K\) quá lớn (\(K > 25\)): Thuật toán duyệt bitmask có độ phức tạp \(O(2^K)\). Khi \(K = 30\), số trạng thái là \(2^{30} \approx 10^9\), chắc chắn sẽ bị TLE. Đối với các bài toán có \(K\) lớn nhưng các phần tử có tính đối xứng hoặc giá trị trùng lặp, ta cần gom nhóm các tập có cùng lực lượng giao điểm để chuyển sang quy hoạch động đếm tổ hợp trong thời gian đa thức.
Luyện ngay trên Big-O Coding
Để làm chủ kỹ thuật duyệt bitmask kết hợp bù trừ, bạn hãy thực hành ngay bài tập sau trên Big-O Coding:
Làm thế nào để tránh tràn số khi nhân nhiều số nguyên tố trong bitmask?
Khi duyệt các bit trong mask, tích prod có thể tăng theo cấp số nhân và vượt quá giới hạn \(2^{63} - 1\) của kiểu long long. Thay vì thực hiện phép nhân trực tiếp prod *= p rồi so sánh với \(N\), bạn phải luôn kiểm tra điều kiện an toàn trước: if (prod > n / p) break;. Phép chia \(N / p\) đảm bảo không bao giờ bị tràn số nguyên.
Nguyên lý bù trừ có áp dụng được khi số tập hợp K lớn hơn 30 không?
Khi \(K > 30\), việc duyệt \(2^K\) trạng thái sẽ bị TLE vì \(2^{30} \approx 10^9\). Trong trường hợp này, nếu bài toán có cấu trúc đối xứng hoặc các tập hợp có kích thước giống nhau, ta chuyển sang phương pháp quy hoạch động (DP) kết hợp hệ số tổ hợp, hoặc sử dụng biến đổi Moebius (SOS DP / Fast Walsh-Hadamard Transform).
Nguồn tham khảo
- CP-Algorithms - The Inclusion-Exclusion Principle - Hướng dẫn chi tiết và các biến thể nâng cao của nguyên lý bù trừ
- VNOI Wiki - Bao hàm loại trừ - Chuyên đề tổ hợp nâng cao dành cho đội tuyển thi quốc gia
- USACO Guide - Inclusion-Exclusion Principle - Bộ bài tập chọn lọc có lời giải về Bitmask và nguyên lý bù trừ
Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.


