Mình xin chia sẻ lời giải bài này như sau:

• Theo mình đây là bài toán vận dụng ở mức ở cơ bản về bitmask, nên lời giải này, mình sẽ cố gắng viết từ cái cơ bản để những bạn nào chưa biết bitmask là gì có thể hiểu được và áp dụng

• Lời giải này, mình sẽ chia làm \(2\) phần:

• Phần 1: Lý thuyết và những phép toán thường dùng trên bitmask

• Phần 2: Áp dụng phần 1 để giải quyết bài toán đề ra.

Bây giờ, ta sẽ đi đến phần 1: Lý thuyết và những phép toán thường dùng trên bitmask

Mình sẽ tiếp cận bitmask này thông qua một bài toán kinh điển như sau :

Bài toán: Cho tập hợp \(S=\left\{1,2,3,...,n\right\}\) với \(n\) nguyên dương. Hỏi tập \(S\) này có bao nhiêu tập con và liệt kê chúng !

• Đầu tiên, ta sẽ đi đến với câu hỏi thứ nhất : Tập \(S\) này có bao nhiêu tập con ?

Thì để trả lời được câu hỏi này, ta có \(2\) tiếp cận chính:

• Cách \(1\): Dùng nhị thức Newton và công thức tổ hợp

• Cách \(2\): Đếm trên bit sử dụng phương pháp song ánh

Mình sẽ trình bày cả \(2\) cách để các bạn nắm nhé, và đặc biệt là cách \(2\) sẽ đem đến cho ta những kiến thức căn bản về bitmask, từ đó ta có thể áp dụng những bài toán khác tương tự !

Cách 1: Dùng nhị thức Newton và công thức tổ hợp

Ta nhận thấy rằng những tập hợp con của \(S\) được chia thành các dạng như sau:

• Tập hợp rỗng

• Tập hợp con có \(1\) phần tử

• Tập hợp con có \(2\) phần tử

...

• Tập hợp con có \(n\) phần tử.

Và số lượng tập hợp con có \(i\) phần tử với \(0\le i\le n\) là \(\binom{n}{i}\)

Do đó: Số lượng tập con của tập \(S\) là: \(\sum\limits_{i=0}^{n}\binom{n}{i}\)

Mặt khác, theo theo nhị thức Newton ta có: \((x+1)^{n}=\binom{n}{0}x^{n}.1^{0}+\binom{n}{1}x^{n-1}.1^{1}+...+\binom{n}{n}x^{0}.1^{n}\implies (1)\)

Thay \(x=1\) vào \((1)\) ta được: \(2^{n}=\binom{n}{0}+\binom{n}{1}+...+\binom{n}{n}=\sum\limits_{i=0}^{n}\binom{n}{i}\)

Do đó số lượng tập con của \(S\) là: \(2^{n}\)

Cách 2: Đếm trên bit

Gọi \(U\) là tập hợp tất cả các xâu nhị phân có \(n\) phần tử (chỉ số của các xâu nhị phân này được đánh số từ phải sang trái và bắt đầu bằng \(1\)). Khi đó theo quy tắc nhân ta có: \(|U|=2^{n}\). (ở đây: \(|U|\) là số lượng phần tử có trong tập \(U\))

Gọi \(V\) là tập hợp tất cả các tập con của tập \(S\)

Ý tưởng của cách \(2\) này là ta đi thiết lập một song ánh \(f: U\rightarrow V\) và từ đây theo tính chất của song ánh ta suy ra được \(|V|=|U|=2^{n}\)

Thật vậy, ta thiết lập một song ánh như sau:

Ta xét một phần tử \(u\) bất kì của tập \(U\), và giả sử rằng: \(u=\overline{a_{n}a_{n-1}..a_{1}}\) với \(a_i\in \left\{0,1\right\}(\forall 1\le i\le n)\)

và xét một tập hợp \(v\) bất kì của tập \(V\), và giả sử rằng, tập hợp \(v\) này có \(k(0\le k\le n)\) phần tử đó là: \(v=\left\{v_1,v_2,...,v_k\right\}(v_i \in S)\)

Khi đó ta định nghĩa: \(u\) tương đương với \(v\) nếu các bít thứ \(v_1,v_2,...,v_k\) trong \(u\) được bật lên và các bit còn lại đều tắt.

Và ta kí hiệu: \(u\) tương đương với \(v\) là \(u\iff v\)

Khi đó ta nhận thấy rằng, ứng với mỗi \(u\) trong \(U\) chỉ tồn tại duy nhất một \(v\) trong \(V\) thoả mãn \(u\iff v\) và ngược lại, ứng với mỗi \(v\) trong \(V\) chỉ tồn tại duy nhất một \(u\) trong \(U\) thoả mãn \(u\iff v\)

Và từ đây ta có điều phải chứng minh !

Chứng minh là vậy đó, nhưng để dễ hiểu hơn, chúng ta sẽ đi tìm hiểu một ví dụ nho nhỏ để hiểu được ý tưởng của cách \(2\), và cũng thông qua cách này, ta sẽ biết cách liệt kê những tập con của tập \(S\) một cách dễ dàng

Các bạn tiếp tục đón xem nhé !

Giả sử \(n=3\), tức ta có \(S=\left\{1,2,3\right\}\)

Khi đó ta có: \(U=\left\{000,001,010,100,011,101,110,111\right\}\)

Và \(V=\left\{\left\{\emptyset \right\},\left\{1 \right\},\left\{2 \right\},\left\{3 \right\},\left\{1,2 \right\},\left\{1,3 \right\},\left\{2,3 \right\},\left\{1,2,3 \right\}\right\}\)

Theo chứng minh của cách \(2\) trên ta sẽ có những cặp phần tử sau tương đương với nhau (các bạn chú ý là chỉ số của các xâu được đánh số từ phải sang trái và bắt đầu từ \(1\) nhé !)

• \(000 \iff \left\{\emptyset \right\}\)

• \(001 \iff \left\{1 \right\}\)

• \(010 \iff \left\{2 \right\}\)

• \(100 \iff \left\{3 \right\}\)

• \(011 \iff \left\{1,2 \right\}\)

• \(101 \iff \left\{1,3 \right\}\)

• \(110 \iff \left\{2,3 \right\}\)

• \(111 \iff \left\{1,2,3 \right\}\)

Để giúp các bạn khắc sâu hơn phần này mình xin lấy thêm một ví dụ khác:

Hỏi: Giả sử ta có tập \(S=\left\{1,2,3,4,5,6\right\}\), hãy tìm xâu nhị phân tương đương với tập con sau: \(v=\left\{1,3,5,4\right\}\)

Đáp: Xâu nhị phân tương đương là \(011101\)

Như vậy là thông qua bài toán này, mình hy vọng các bạn học thêm được một cách biểu diễn tập hợp mới, đó là biểu diễn thông qua xâu nhị phân, và việc này có ý nghĩa cực kì quan trọng, giúp các bạn dễ dàng trong việc thực hiện các phép tính toán trên tập hợp như, phép giao, phép hợp, ... Và không để các bạn chờ đợi lâu, mình sẽ tiếp tục qua phần những phép toán trên xâu ! Các bạn tiếp tục đón xem nhé !

Để giúp các bạn dễ hiểu, mình sẽ lấy ví dụ cụ thể nhé !

Giả sử ta có: \(S\left\{1,2,3,4,5,6,7,8\right\}\) và hai tập con của \(S\) là: \(A=\left\{1,2,6,5,7\right\}\) và \(B=\left\{3,2,4,7\right\}\)

Và nhiệm vụ của ta là bây giờ đi tìm \(P_1 = A\cap B\) và \(P_2 = A\cup B\)

Gọi \(r(A),r(B),r(P_1),r(P_2)\) lần lượt là các xâu nhị phân tương đương với \(A,B,P_1,P_2\) khi đó ta có

\(r(A)=01110011\) và \(r(B)=01001110\)

Khi đó: \(r(P_1)=r(A)|r(B)\) và \(r(P_2)=r(A) \text{&} r(B)\)

Từ đây ta dễ dàng suy ra được:

• \(r(P_1)=01111111\) và \(r(P_2)=01000010\)

Từ đây ta suy ra được \(P_1 = \left\{1,2,3,4,5,6,7\right\}\) và \(P_2 = \left\{2,7\right\}\)

Tiếp theo, mình giới thiệu một số phép toán về bit rất phổ biến để ta áp dụng vào phần code của mình.

• Phép toán dịch trái: \(1\ll n\)

• Phép toán kiểm tra bit thứ j trong xâu \(i\) bật hay tắt:

• Cách 1: \((1\ll j)\text{&}i\)

• Cách 2: \((i\gg j)\text{&}1\)

Ps: Để biết được phép dịch trái, phép dịch phải là gì, các bạn cứ lên mạng search GG là có nhé ! Ở đây mình chỉ trình bày phần kết quả

Bây giờ, ta áp dụng những kiến thức này để giải bài toán ban đầu nhé !

• Ý tưởng của bài toán này, là ta sẽ xây dựng một mảng \(s\) để đánh dấu những tập hợp nào có khả năng được tạo thành từ những tập hợp đã cho !

Và thuật toán để xây dựng mảng \(s\) như sau:

Ý tưởng chính của bài này đó là: Ta sẽ biểu diễn các tập hợp từ input đã cho thành những xâu nhị phân và biểu diễn xâu nhị phân này dưới dạng số thập phân, sau đó ứng với mỗi tập hợp đọc vào từ input, ta duyệt qua tất cả các tập con của tập hợp gồm \(n\) phần tử để kiểm tra xem có tập con nào đã tồn tại trước đó, và ta việc lấy hợp của từng tập hợp đọc từ input với tất cả các tập con tồn tại trước đó, nó sẽ tạo nên một tập hợp mới , và ta dùng mảng bit để đánh dấu lại !

Cuối cùng ta dùng một vòng for để đếm là xong

Như vậy là bài toán đã được giải quyết hoàn tất

Các bạn có thể xem code của mình tại đây

Cảm ơn các bạn đã cố gắng đọc hết solution, mình hy vọng các bạn có thể hiểu được

Ps: Nếu có gì không hiểu hoặc sai sót, các bạn nhớ comment bên dưới nhé !