Nguyên lý bao hàm loại trừ

Nguyên lý bao hàm loại trừ (inclusion-exclusion principle) là công cụ đếm số phần tử thuộc ít nhất một trong các tập $A_1,\dots ,A_k$ (hoặc không thuộc tập nào) khi các tập giao nhau chằng chịt. Thay vì đếm trực tiếp hợp (thường rất khó), ta chỉ cần đếm các giao, vốn dễ hơn nhiều: "chia hết cho cả $2$ lẫn $3$" dễ đếm hơn "chia hết cho $2$ hoặc $3$". Với $k$ tập nhỏ, duyệt $2^k$ tập con bằng bitmask cho lời giải $O(2^k·k)$, trong khi cách ngây thơ là duyệt từng phần tử của tập vũ trụ (có thể tới ${10}^{18}$ phần tử).

Trong cả trang, $k$ luôn là số tập (số tính chất) đang xét.

Ý tưởng / Trực giác

Từ hai tập đến ba tập

Với hai tập, cộng $|A|+|B|$ thì phần giao $A\cap B$ bị đếm hai lần, nên trừ đi một lần:

$$|A\cup B|=|A|+|B|-|A\cap B|.$$

Với ba tập, sau khi cộng ba tập và trừ ba giao đôi một, phần tử nằm trong cả ba tập đã được cộng $3$ lần rồi trừ $3$ lần, tức là đang bị đếm $0$ lần. Phải cộng lại:

$$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.$$

  Số lần mỗi vùng được đếm qua từng bước (ba tập A, B, C)

  vùng                 +đơn   -đôi   +ba   tổng
  chỉ A                  1      0     0      1
  A và B (không C)       2     -1     0      1
  cả A, B, C             3     -3    +1      1

Công thức tổng quát

Với $k$ tập $A_1,\dots ,A_k$ và với mỗi tập con khác rỗng $S\subseteq \{1,\dots ,k\}$, đặt $A_S={\bigcap }_{i\in S}{A}_i$:

$$|A_1\cup \dots \cup A_k|=\sum _{\varnothing \ne S}(-1{)}^{|S|+1}|A_S|.$$

Trong thực tế, dạng hay dùng hơn là đếm phần tử của tập vũ trụ $U$ không thuộc tập nào (quy ước $A_{\varnothing }=U$):

$$|U⧵(A_1\cup \dots \cup A_k)|=\sum _{S\subseteq \{1..k\}}(-1{)}^{|S|}|A_S|.$$

Mẹo nhận diện: đề hỏi "không có tính chất xấu nào" (không chia hết cho số nào, không có điểm cố định, không vượt giới hạn của hộp nào...) thì gọi $A_i$ là tập vi phạm điều kiện thứ $i$. Việc đếm "vi phạm đồng thời một nhóm điều kiện $S$" thường có công thức đóng.

Vì sao mỗi phần tử được đếm đúng một lần

Xét một phần tử $x$ thuộc đúng $t$ tập. Ở dạng "không thuộc tập nào", $x$ góp vào số hạng của $S$ khi và chỉ khi $S$ là tập con của $t$ tập chứa $x$. Có $\left(\genfrac{}{}{0ex}{}{t}{j}\right)$ cách chọn $S$ gồm $j$ tập như vậy, nên tổng đóng góp của $x$ là

$$\sum _{j=0}^t(-1{)}^j(\genfrac{}{}{0ex}{}{t}{j})=(1-1{)}^t=\{\begin{array}{cc}1\hfill & t=0\hfill \\ 0\hfill & t\ge 1.\hfill \end{array}$$

Đây là khai triển nhị thức Newton của $(1-1{)}^t$. Phần tử không thuộc tập nào ($t=0$) chỉ nằm trong số hạng $S=\varnothing$ nên được đếm đúng $1$ lần; mọi phần tử "xấu" bị triệt tiêu hoàn toàn. Dạng hợp chỉ là $|U|$ trừ đi dạng này.

Ví dụ chạy tay

Đếm số $x\in [1,30]$ không chia hết cho $2$, $3$, $5$. Gọi $A_p$ là tập các số chia hết cho $p$. Vì $2,3,5$ nguyên tố cùng nhau, "chia hết cho mọi số trong $S$" tương đương "chia hết cho tích của chúng", nên $|A_S|=\lfloor 30/{\prod }_{p\in S}p\rfloor$.

Duyệt $2^3=8$ mặt nạ bit (bit $0$ ứng với $2$, bit $1$ với $3$, bit $2$ với $5$):

Tổng: $30-31+10-1=8$. Kiểm tra: đó là $1,7,11,13,17,19,23,29$.

Theo dõi riêng hai số để thấy "đếm đúng một lần":

 x = 6  (chia hết cho 2 và 3, t = 2)
   có mặt ở:  {}  {2}  {3}  {2,3}
   dấu:       +1   -1   -1   +1     => tổng 0   (bị loại, đúng)

 x = 30 (chia hết cho 2, 3, 5, t = 3)
   có mặt ở:  {}  {2} {3} {5}  {2,3} {2,5} {3,5}  {2,3,5}
   dấu:       +1  -1  -1  -1    +1    +1    +1     -1     => tổng 0

 x = 7  (t = 0)
   có mặt ở:  {}                                           => tổng 1

Cài đặt

C++

Đếm số $x\in [1,n]$ không chia hết cho bất kỳ số nguyên tố nào trong danh sách. Tích có thể tràn long long khi $n$ tới ${10}^{18}$, nên dừng sớm khi tích vượt $n$ (khi đó $\lfloor n/\text{tích}\rfloor =0$).

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

// Count x in [1, n] divisible by none of the given primes.
ll countFree(ll n, const vector<ll>& primes) {
    int k = primes.size();
    ll result = 0;
    for (int mask = 0; mask < (1 << k); mask++) {
        ll prod = 1;
        bool tooBig = false;
        for (int i = 0; i < k; i++)
            if (mask >> i & 1) {
                if (prod > n / primes[i]) { tooBig = true; break; }  // product exceeds n: term is 0
                prod *= primes[i];
            }
        if (tooBig) continue;
        ll term = n / prod;                                  // numbers divisible by all chosen primes
        if (__builtin_popcount(mask) % 2 == 0) result += term;
        else result -= term;
    }
    return result;
}

int main() {
    ll n; int k;
    cin >> n >> k;
    vector<ll> primes(k);
    for (auto& p : primes) cin >> p;
    cout << countFree(n, primes) << "\n";   // input "30 3 2 3 5" -> 8
}

Muốn đếm số chia hết cho ít nhất một số nguyên tố, lấy $n-\mathtt{\text{countFree}}(n)$. Muốn đếm trên đoạn $[L,R]$, lấy $\mathtt{\text{countFree}}(R)-\mathtt{\text{countFree}}(L-1)$.

Python

Số nguyên Python không tràn nên không cần kiểm tra tích.

def count_free(n, primes):
    """Count x in [1, n] divisible by none of the primes."""
    k = len(primes)
    result = 0
    for mask in range(1 << k):
        prod = 1
        for i in range(k):
            if mask >> i & 1:
                prod *= primes[i]
        sign = -1 if bin(mask).count("1") % 2 else 1
        result += sign * (n // prod)   # Python ints never overflow
    return result

n, k, *primes = map(int, open(0).read().split())
print(count_free(n, primes))

Độ phức tạp

• Thời gian: $O(2^k·k)$. Có $2^k$ tập con, mỗi tập con tính tích trong $O(k)$. Có thể giảm còn $O(2^k)$ bằng cách lưu giá trị của từng mặt nạ và suy ra val[mask] từ val[mask & (mask - 1)] (bỏ bit thấp nhất), như trong mục giao hình chữ nhật bên dưới.
• Bộ nhớ: $O(k)$ với cách tính lại tích, $O(2^k)$ nếu lưu giá trị cho mọi mặt nạ.
• Giới hạn thực tế: $2^k$ chỉ chấp nhận được khi $k\lesssim 20$ đến $25$. May mắn là số lượng ước nguyên tố phân biệt của một số $\le {10}^{18}$ không quá $15$ (tích $15$ số nguyên tố đầu tiên $2·3\cdots 47\approx 6,1·{10}^{17}$, nhân thêm $53$ là vượt ${10}^{18}$), và của một số $\le {10}^6$ không quá $7$, nên bài "đếm số nguyên tố cùng nhau với $p$" luôn chạy nhanh.

⚠️ Lỗi thường gặp

• Dừng ở giao đôi một. Triệu chứng: đúng với $k=2$, sai khi $k\ge 3$. Công thức phải đi qua mọi kích thước tập con, dấu đổi luân phiên theo $|S|$. Duyệt bitmask thì không bao giờ quên tầng nào.
• Dùng tích thay cho BCNN. Nếu các số không đôi một nguyên tố cùng nhau (ví dụ $4$ và $6$), "chia hết cho cả hai" là chia hết cho $lcm(4,6)=12$, không phải $24$. Cách tránh: phân tích ra thừa số nguyên tố phân biệt trước, hoặc tính lcm thay cho tích (và vẫn kiểm tra tràn).
• Tràn số khi nhân tích. Với $n\le {10}^{18}$, tích vài số nguyên tố lớn vượt long long. Kiểm tra prod > n / p trước khi nhân; khi vượt thì số hạng bằng $0$, bỏ qua.
• Sai dấu hoặc lẫn hai dạng công thức. Dạng "không thuộc tập nào" có số hạng $S=\varnothing$ mang dấu $+$ và dấu là $(-1{)}^{|S|}$; dạng "hợp" bỏ $S=\varnothing$ và dấu là $(-1{)}^{|S|+1}$. Trộn hai dạng làm lệch đúng $|U|$ hoặc đổi dấu toàn bộ. Tự kiểm tra bằng một input tay nhỏ như $n=30$ ở trên.
• Modulo âm. Khi đáp án lấy theo modulo, (s - term) % MOD có thể âm trong C++. Viết (s - term % MOD + MOD) % MOD.
• Trùng phần tử trong danh sách. Nếu danh sách số nguyên tố có lặp (ví dụ đọc thừa số của $12=2·2·3$ mà không khử trùng), mỗi số nguyên tố bị coi là hai tập khác nhau và kết quả sai. Khử trùng trước khi duyệt.
• $k$ quá lớn. Với $k=40$ thì $2^{40}$ tập con là không khả thi. Khi đó cần gộp các tập con có cùng số hạng: theo kích thước $|S|$ (khi $|A_S|$ chỉ phụ thuộc $|S|$, như derangement), theo ước số (hàm Möbius), hoặc theo mặt nạ giá trị (SOS DP). Xem mục Biến thể.
• Lưu mảng $2^k$ phần tử quá lớn. Cách lưu giá trị cho mọi mặt nạ tốn $2^k$ ô nhớ nhân kích thước mỗi ô. Ví dụ mảng Rect (bốn long long, $32$ byte) ở mục giao hình chữ nhật: $k=16$ tốn $2$ MB, nhưng $k=20$ đã tốn $32$ MB. Khi $k$ lớn, duyệt tập con bằng đệ quy (DFS thêm dần từng tập, giữ giao hiện tại trên ngăn xếp) chỉ tốn $O(k)$ bộ nhớ.

Biến thể / Mở rộng

Hoán vị không điểm cố định (derangement)

Đếm số hoán vị $p$ của $\{1,\dots ,n\}$ mà $p_i\ne i$ với mọi $i$. Gọi $A_i$ là tập hoán vị có $p_i=i$. Cố định một tập $S$ gồm $j$ vị trí thì các vị trí còn lại hoán vị tùy ý: $|A_S|=(n-j)!$, chỉ phụ thuộc $j=|S|$. Gộp $\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ tập con cùng kích thước:

$$D_n=\sum _{j=0}^n(-1{)}^j(\genfrac{}{}{0ex}{}{n}{j})(n-j)!=n!\sum _{j=0}^n\frac{(-1{)}^j}{j!}.$$

Nhờ gộp theo kích thước, $2^n$ số hạng thu về $n+1$ số hạng, nên tính một giá trị $D_n$ mất $O(n)$ (sau khi có sẵn giai thừa, xem Tổ hợp). Nếu cần cả bảng $D_0..D_n$ mà gọi công thức này cho từng $m$ thì tốn $O(n^2)$; thay vào đó dùng công thức truy hồi tương đương $D_n=(n-1)(D_{n-1}+D_{n-2})$, cả bảng trong $O(n)$. Dãy đầu: $D_0..D_7=1,0,1,2,9,44,265,1854$. Tỷ lệ $D_n/n!\to 1/e\approx 0,3679$.

// One D_n mod MOD by inclusion-exclusion, O(n); needs fact[], C(a, b).
ll derange(int n) {
    ll d = 0;
    for (int j = 0; j <= n; j++) {
        ll term = C(n, j) * fact[n - j] % MOD;   // sum of |A_S| over all S with |S| = j
        d = (j % 2 == 0) ? (d + term) % MOD : (d - term + MOD) % MOD;
    }
    return d;
}

// Whole table D_0..D_n in O(n) via the recurrence.
D[0] = 1;
if (n >= 1) D[1] = 0;
for (int m = 2; m <= n; m++) D[m] = (ll)(m - 1) * ((D[m - 1] + D[m - 2]) % MOD) % MOD;

Biến thể hay gặp: chỉ một số vị trí bị cấm (ví dụ $m$ vị trí "nguy hiểm" trong $q$ vị trí trống, các giá trị còn thiếu cũng có $q$ giá trị). Khi đó đáp án là ${\sum }_{j=0}^m(-1{)}^j(\genfrac{}{}{0ex}{}{m}{j})(q-j)!$.

Từ "ít nhất" sang "đúng $r$" (nghịch đảo nhị thức)

Nhiều bài hỏi số đối tượng có đúng $r$ tính chất (trong $k$ tính chất). Đặt

$$g_j=\sum _{|S|=j}|A_S|$$

(tổng theo mọi nhóm $j$ tính chất, mỗi đối tượng có $t$ tính chất được đếm $\left(\genfrac{}{}{0ex}{}{t}{j}\right)$ lần, không phải "số đối tượng có ít nhất $j$ tính chất"). Nếu $e_t$ là số đối tượng có đúng $t$ tính chất thì $g_j={\sum }_{t\ge j}\left(\genfrac{}{}{0ex}{}{t}{j}\right)e_t$, và nghịch đảo nhị thức cho

$$e_r=\sum _{j\ge r}(-1{)}^{j-r}(\genfrac{}{}{0ex}{}{j}{r})g_j.$$

Với $r=0$ đây chính là công thức "không thuộc tập nào". Ví dụ với hoán vị $n=6$ và tính chất "$p_i=i$": $g_j=\left(\genfrac{}{}{0ex}{}{6}{j}\right)(6-j)!$ cho $g=[720,720,360,120,30,6,1]$, và công thức trên cho số hoán vị có đúng $r$ điểm cố định:

 r      0     1     2     3     4     5     6
 e_r   265   264   135    40    15     0     1      (tổng = 720 = 6!)

(Kiểm chứng: $e_r=\left(\genfrac{}{}{0ex}{}{6}{r}\right)D_{6-r}$, ví dụ $e_2=15·9=135$.)

Bao hàm loại trừ trên tập con: SOS DP và nghịch đảo Möbius

Khi các "tập" là các bit của một mặt nạ, bao hàm loại trừ trở thành phép biến đổi trên dàn tập con. Giả sử ta cần $f(v)$ = số đối tượng có đặc trưng đúng bằng $v$ (ví dụ OR của tập được chọn bằng đúng $v$), nhưng chỉ dễ tính

$$g(m)=\sum _{v\subseteq m}f(v)$$

(đặc trưng là tập con của $m$). Khi đó bao hàm loại trừ cho

$$f(v)=\sum _{m\subseteq v}(-1{)}^{|v|-|m|}g(m).$$

Tính trực tiếp là $O(3^B)$; dùng quy hoạch động tổng trên tập con (SOS DP) với phép trừ thay cho phép cộng thì mọi $f(v)$ có trong $O(B·2^B)$. Ví dụ: đếm, với mọi $v$, số tập con khác rỗng của dãy $a$ có OR đúng bằng $v$. OR là tập con của $m$ khi và chỉ khi từng phần tử là tập con của $m$, nên $g(m)=2^{\mathit{c}\mathit{n}\mathit{t}(m)}-1$ với $\mathit{c}\mathit{n}\mathit{t}(m)$ là số $a_i\subseteq m$.

// cnt has size 2^B, cnt[x] = how many a_i equal x. pw[i] = 2^i mod MOD.
for (int b = 0; b < B; b++)                        // zeta: cnt[m] = #a_i that are submasks of m
    for (int m = 0; m < (1 << B); m++)
        if (m >> b & 1) cnt[m] += cnt[m ^ (1 << b)];

vector<ll> f(1 << B);
for (int m = 0; m < (1 << B); m++) f[m] = (pw[cnt[m]] - 1 + MOD) % MOD;   // g(m)

for (int b = 0; b < B; b++)                        // Mobius: undo the zeta transform
    for (int m = 0; m < (1 << B); m++)
        if (m >> b & 1) f[m] = (f[m] - f[m ^ (1 << b)] + MOD) % MOD;
// now f[v] = number of non-empty subsets with OR exactly v

Chạy tay với $a=[1,2,3,1]$, $B=2$:

 m (nhị phân)    00    01    10    11
 cnt(m)           0     2     1     4      (a_i là tập con của m)
 g(m)=2^cnt-1     0     3     1    15
 f(v)             0     3     1    11      (11 = 15 - 3 - 1 + 0)

Kiểm tra: tập con có OR bằng 01 chỉ gồm các số $1$: $\{1\},\{1^{\prime }\},\{1,1^{\prime }\}$, đúng $3$.

Dạng đối xứng với AND (đếm siêu tập thay cho tập con) xuất hiện trong bài Jzzhu và những con số (jzzhunum): đếm nhóm có AND bằng $0$.

Tương tự, với điều kiện chia hết thay cho tập con bit, ta được nghịch đảo Möbius trên ước: số cặp có $gcd=1$ bằng ${\sum }_d\mu (d)·(\text{số cặp cùng chia hết cho }d)$. Hàm $\mu (d)$ chính là hệ số bao hàm loại trừ $(-1{)}^{|S|}$ trên tập ước nguyên tố của $d$ (và bằng $0$ khi $d$ có ước chính phương). Xem Hàm nhân tính.

Giao các hình chữ nhật (bài hình học)

Đếm số ô lưới nằm trong hợp của $k$ hình chữ nhật song song trục (mỗi hình cho bằng chỉ số ô, hai biên đều bao gồm), với $k$ nhỏ. Giao của các hình chữ nhật song song trục vẫn là một hình chữ nhật: $[max{x}_1,min{x}_2]\times [max{y}_1,min{y}_2]$, rỗng khi đầu lớn hơn cuối. Vậy mỗi số hạng $|A_S|$ tính trong $O(1)$: số ô là $(x_2-x_1+1)(y_2-y_1+1)$. Nếu cần tổng giá trị ô thay cho số ô, thay công thức này bằng tổng tiền tố hai chiều. Với hình chữ nhật tọa độ thực (tính diện tích), cách làm giữ nguyên, chỉ đổi số hạng thành $(x_2-x_1)(y_2-y_1)$ và coi giao rỗng khi $x_1\ge x_2$ hoặc $y_1\ge y_2$.

struct Rect { ll x1, y1, x2, y2; };   // cells x1..x2, y1..y2 (inclusive)

// Number of grid cells covered by at least one rectangle.
// Keep k small (e.g. k <= 16): inter[] holds 2^k Rects of 32 bytes (k = 20 needs 32 MB).
ll unionCells(const vector<Rect>& r) {
    int k = r.size();
    vector<Rect> inter(1 << k);           // inter[mask] = intersection of rectangles in mask
    ll total = 0;
    for (int mask = 1; mask < (1 << k); mask++) {
        int low = __builtin_ctz(mask);    // lowest chosen rectangle
        int rest = mask & (mask - 1);     // mask without it (already computed)
        if (rest == 0) inter[mask] = r[low];
        else {
            Rect a = inter[rest], b = r[low];
            inter[mask] = {max(a.x1, b.x1), max(a.y1, b.y1), min(a.x2, b.x2), min(a.y2, b.y2)};
        }
        Rect c = inter[mask];
        if (c.x1 > c.x2 || c.y1 > c.y2) continue;             // empty intersection
        ll cells = (c.x2 - c.x1 + 1) * (c.y2 - c.y1 + 1);      // inclusive cell count
        total += (__builtin_popcount(mask) & 1) ? cells : -cells;
    }
    return total;
}

Ví dụ: $A=[1,3]\times [1,3]$, $B=[2,4]\times [2,4]$, $C=[3,5]\times [1,2]$ (tọa độ ô).

 y
 4   .    B    B    B    .        |A| = 9, |B| = 9, |C| = 6
 3   A    AB   AB   B    .        |A∩B| = 4, |A∩C| = 2, |B∩C| = 2
 2   A    AB   ABC  BC   C        |A∩B∩C| = 1  (ô x = 3, y = 2)
 1   A    A    AC   C    C
     1    2    3    4    5   x    hợp = 24 - 8 + 1 = 17 ô

Nhờ lấy giao tăng dần theo mask & (mask - 1), mỗi mặt nạ chỉ tốn $O(1)$, tổng $O(2^k)$ thời gian và $O(2^k)$ bộ nhớ. Khi $k$ lớn (hàng nghìn hình) thì bao hàm loại trừ không dùng được nữa; chuyển sang đường quét (sweep line) với cây phân đoạn.

Bao hàm loại trừ cho bài chia kẹo có chặn trên

Đếm số nghiệm nguyên $x_1+\dots +x_n=s$ với $0\le x_i\le f_i$. Không có chặn trên thì đáp án là $\left(\genfrac{}{}{0ex}{}{s+n-1}{n-1}\right)$ (chia kẹo Euler). Gọi $A_i$ là tập nghiệm có $x_i>f_i$; đặt $x_i^{\prime }=x_i-(f_i+1)$ thì $|A_S|=\left(\genfrac{}{}{0ex}{}{s-{\sum }_{i\in S}(f_i+1)+n-1}{n-1}\right)$ (bằng $0$ nếu tổng bị âm). Duyệt $2^n$ tập con là xong. Khi $s$ rất lớn, tổ hợp $\left(\genfrac{}{}{0ex}{}{N}{n-1}\right)$ với $n$ nhỏ tính trực tiếp bằng tích $n-1$ thừa số nhân nghịch đảo của $(n-1)!$, hoặc bằng định lý Lucas khi modulo nhỏ.

Bài tập luyện

Luyện kỹ thuật

• Đếm cặp nguyên tố cùng nhau (cntcopair) (Nâng cao) đếm cặp có $gcd=1$ bằng cách đếm số phần tử chia hết cho từng $d$ rồi cộng trừ theo $\mu (d)$: bao hàm loại trừ trên các ước nguyên tố, gộp theo ước số.
• Hoán vị không điểm cố định (permnofp) (Kỳ cựu) biến thể của derangement: chỉ những vị trí trống mà giá trị cùng chỉ số cũng đang thiếu mới có thể thành điểm cố định, bao hàm loại trừ theo số vị trí "nguy hiểm" bị vi phạm.
• Dãy số nguyên tố cùng nhau (kthcopr) (Kỳ cựu) đếm số $y\le M$ nguyên tố cùng nhau với $p$ bằng bao hàm loại trừ trên tối đa $7$ ước nguyên tố của $p$, rồi tìm kiếm nhị phân phần tử thứ $k$.
• Tính tương thích bò (cowcompat) (Kỳ cựu) bitmask trên tập thuộc tính: với mỗi con bò, duyệt $2^5-1$ tập con khác rỗng các vị kem, dùng bảng băm đếm số bò chứa tập con đó; cộng trừ theo kích thước tập con ra số cặp có chung ít nhất một vị, lấy phần bù.
• Devu và những bông hoa (devuflower) (Chuyên gia) bài chia kẹo có chặn trên ở mục Biến thể: $2^{20}$ tập hộp bị vượt, mỗi tập một tổ hợp $\left(\genfrac{}{}{0ex}{}{N}{n-1}\right)$ với $N$ tới ${10}^{14}$.

Đề VOI

• Đường đi trên lưới (voi06_path) (Nâng cao) VOI 2006: khung chính là quy hoạch động đếm đường theo ô; bao hàm loại trừ chỉ là bước tăng tốc trong công thức quy hoạch động đó: điều kiện "ước chung lớn hơn $1$" nghĩa là có chung ít nhất một ước nguyên tố, nên bao hàm loại trừ trên tập ước nguyên tố (tối đa $5$) biến tổng khó thành vài tổng "chia hết cho $d$" dễ duy trì.
• Phần thưởng (voi18_bonus) (Nâng cao) VOI 2018: mỗi phương án là hợp của tối đa $5$ hình vuông; hãy nghĩ xem giao của các hình vuông có hình dạng gì và tính tổng trên nó nhanh thế nào.
• Phép toán OR (voi21_or) (Nâng cao) VOI 2021: "OR đúng bằng $v$" khó đếm, nhưng "OR là tập con bit của $m$" thì dễ; tìm cách đi từ cái dễ sang cái khó cho mọi $v$ cùng lúc.
• Thiết bị thông minh (voi23_sdev) (Kỳ cựu) VOI 2023: riêng subtask $N\le 15$ có thể làm bằng bao hàm loại trừ trên $2^N$ tập hình chữ nhật (giao vẫn là hình chữ nhật, số điểm dưới đường $x+y=D$ có công thức đóng); lời giải đầy đủ cần kỹ thuật khác.