+7

Thao tác xử lý bit và ứng dụng (Bit Manipulation)

I. Tổng quan về bit và xử lý bit

Chúng ta đều biết rằng máy tính làm việc với các giá trị nhị phân 01,0 - 1, gọi là các bit, nhờ vậy máy tính hoạt động vô cùng nhanh. Trong lập trình thi đấu, việc áp dụng các bit nhị phân để xử lý bài toán là một kĩ thuật cực kì thú vị, không chỉ giúp cho tốc độ thuật toán được cải thiện đáng kể, mà còn làm tối ưu bộ nhớ và đơn giản hóa chương trình. Kĩ thuật này được gọi là Thao tác bit (Bit Manipulation), là kĩ thuật sử dụng các bit của một số nguyên không âm (biểu diễn nhị phân) để biểu diễn một tập hợp, đi kèm với đó là những mẹo để xử lý các bit của một số nguyên.

Trong chuyên đề này, chúng ta sẽ cùng thảo luận về ứng dụng của Thao tác bit trong Lập trình thi đấu và phân tích một số bài tập cụ thể liên quan tới kĩ thuật này. Nhưng trước tiên hãy cùng nhắc lại những kiến thức cơ bản liên quan tới bit!

1. Các toán tử trên bit (Bitwise operators)

Cơ bản

Những thứ cơ bản nhất (cũng là quan trọng nhất) trong thao tác bit là các toán tử trên bit - mà có lẽ ai học lập trình cũng đã từng nghe qua: AND (&), OR (|), XOR (^), NOT (~). Những toán tử này phần nào giống với các toán tử logic &&, ||!, tuy nhiên điều khác biệt là chúng sẽ làm việc trên các bit của hai số nguyên. Bảng chân trị của các toán tử này như sau:

Như vậy, khi sử dụng các toán tử này với hai số nguyên, chẳng hạn như 10 & 5, thì từng cặp bit tương ứng trên biểu diễn nhị phân của hai toán hạng sẽ được so khớp với nhau theo toán tử. Nếu như số lượng bit của hai số khác nhau, thì các chữ số 00 sẽ được tự động thêm vào phía bên trái để độ dài biểu diễn nhị phân của chúng bằng nhau (số lượng chữ số 00 thêm vào phụ thuộc vào kiểu dữ liệu của các số nguyên đó là bao nhiêu bit):

10 = 1010
5 = 0101
10 & 5 = 0000
10 | 5 = 1111
10 ^ 5 = 1111
~A = 0101
~B = 1010

Có hai toán tử thao tác bit nữa là NANDNOR, tuy nhiên không có nhiều tác dụng trong lập trình thi đấu, vì vậy tôi sẽ không đề cập ở đây.

Toán tử dịch bit

Hai toán tử rất thường xuyên sử dụng mà ta cần nắm vững ở đây là dịch trái << và dịch phải >>. Nếu ta viết a << b thì ta đang dịch các bit của aa sang trái bb vị trí, còn nếu viết a >> b thì ta đang dịch các bit của aa sang phải bb vị trí. Đối với các số nguyên không âm, thì khi dịch trái, các bit mới có thể sẽ xuất hiện bên tay phải của số, chúng sẽ bằng 00. Còn khi dịch phải, thì các bit bị dịch sang phải sẽ biến mất, các bit trống bên tay trái sẽ trở thành 00. Ví dụ dưới đây giả định rằng các số nguyên được biểu diễn dưới dạng 88 bit, và tác dụng của các phép dịch trái - dịch phải sẽ như sau:

10 << 2 = 00001010 << 2 = 00101000
10 >> 2 = 00001010 >> 2 = 00000010

Phép dịch trái bb bit tương ứng với việc nhân với 2b,2^b, còn phép dịch phải bb bit tương ứng với việc chia nguyên cho 2b2^b. Hai toán tử này thường xuyên được sử dụng để truy cập vào một bit bất kì của số nguyên - kĩ thuật mà ta sẽ bàn tới ở ngay phía sau.

Lưu ý: Khi tính toán các giá trị a << b mà có khả năng kết quả vượt quá int, các bạn phải tiến hành ép kiểu để tránh bị tràn số. Chẳng hạn như 1 << n là tính 2n,2^n, khi n32n \ge 32 thì giá trị sẽ vượt quá int, vì thế ta phải viết là 1LL << n.

Độ ưu tiên của các toán tử thao tác bit

Bảng dưới đây thể hiện độ ưu tiên của tất cả các loại toán tử trong C++, theo quy tắc các nhóm toán tử có độ ưu tiên cao hơn sẽ ở hàng phía trên của bảng, và các toán tử trong cùng một nhóm sẽ có độ ưu tiên theo quy tắc từ trái sang phải hoặc từ phải sang trái:

Nhìn vào đây, ta có thể thấy các toán tử dịch bit <<>> có độ ưu tiên cao nhất trong các toán tử thao tác bit, tuy nhiên vẫn thấp hơn các phép toán số học +, -, *, /%. Các phép toán gán có sự xuất hiện của thao tác bit cũng sẽ có độ ưu tiên thấp hơn các phép toán gán với toán tử số học. Các bạn cần chú ý điểm này để tránh nhầm lẫn khi tính toán.

2. Sử dụng bit để biểu diễn tập hợp

Biểu diễn tập hợp thông qua biểu diễn nhị phân

Ta có thể lợi dụng biểu diễn nhị phân của một số nguyên lên tới 3232 bit (hoặc 6464 bit nếu như ngôn ngữ lập trình của các bạn có kiểu số nguyên 6464 bit) để biểu diễn một tập hợp, với bit 11 thể hiện rằng phần tử ở vị trí tương ứng có xuất hiện trong tập hợp, và bit 00 để thể hiện phần tử đó không xuất hiện.

Giả sử AABB là hai biểu diễn nhị phân đại diện cho hai tập hợp, thì ta có thể sử dụng các toán tử thao tác bit để thực hiện các phép toán trên hai tập hợp này như sau:

  • Phép toán hợp (Set union): A | B.
  • Phép toán giao (Set intersaction): A & B.
  • Phép toán hiệu (Set subtraction): A & ~B.
  • Phép toán phủ định tập hợp (Set negation): ALL_BITS ^ A - với ALL_BITS là một số nguyên gồm toàn bit 11 với độ dài bằng với độ dài của AA.

"Bật" và "tắt" bit

Ta có thể "bật" (set) một bit ở vị trí nn của số nguyên AA lên với hai bước sau:

  • Bước 11: Tạo số nguyên với bit 11 ở vị trí thứ n,n, các bit còn lại đều bằng 001 << n.
  • Bước 22: Lấy số nguyên AA đem OR với 1 << n. Vậy ta có công thức A |= (1 << n).

Hoàn toàn tương tự, ta có thể "tắt" (clear/unset) một bit ở vị trí nn của số nguyên AA với hai bước sau:

  • Bước 11: Tạo số nguyên với bit 11 ở vị trí thứ n,n, các bit còn lại đều bằng 0,0, rồi phủ định nó bằng toán tử NOT: ~(1 << n).
  • Bước 22: Lấy số nguyên AA đem AND với ~(1 << n). Vậy ta có công thức A &= (~(1 << n)).

Kiểm tra bit đang bật hay tắt

Ta có thể kiểm tra một bit ở vị trí nn của số AA có phải bằng 11 không thông qua các bước sau:

  • Bước 11: Tạo số với bit 11 ở vị trí nn bằng công thức 1 << n.
  • Bước 22: Lấy số AA đem AND với số 1 << n, nếu như bit ở vị trí nn đang bật thì kết quả sẽ khác 0,0, ngược lại thì kết quả sẽ bằng 00. Vậy ta có công thức: A & (1 << n) != 0.

Lật bit

Lật bit là thao tác đảo ngược giá trị của bit, từ 00 thành 11 hoặc từ 11 thành 00. Lợi dụng toán tử XOR, ta có thể đảo bit ở vị trí nn của số AA như sau:

  • Bước 11: Tạo số với bit 11 ở vị trí nn bằng công thức 1 << n.
  • Bước 22: Lấy số AA đem XOR với số 1 << n để thu được số mới đã lật bit tại vị trí nn: A ^= (1 << n).

II. Một số mẹo hay với thao tác bit

Dựa vào bit, chúng ta có thể thực hiện rất nhiều các kĩ thuật với độ tối ưu cao. Trong phần này chúng ta sẽ cùng thảo luận về những kĩ thuật này. Nếu như áp dụng đúng cách, chúng sẽ giúp cho chương trình có tốc độ thực thi rất nhanh và có thể biến code của các bạn từ TLE thành AC ở những kì thi online.

1. Một số hàm builtin quan trọng trong thư viện GCC

Thư viện GCC cung cấp các hàm builtin (là các hàm không cần phải khai báo thư viện nào mà vẫn có thể sử dụng được) rất thú vị, mà có thể sẽ giúp ích trong quá trình giải quyết các bài toán liên quan tới xử lý bit. Dưới đây người viết xin liệt kê nhanh một vài hàm trong số đó:

Hàm __builtin_popcount(x)

Hàm này có tác dụng đếm số lượng bit 11 trong biểu diễn nhị phân của số xx.

Độ phức tạp: O(log2x)O(\log_2 x).

Ví dụ

#include <iostream>

using namespace std;

main()
{
    int n = 5;
    cout << "Count of 1s in binary of " << n << " is " << __builtin_popcount(n);
	
    return 0;
}

Output

Count of 1s in binary of 5 is 2 

Hàm __builtin_parity(x)

Hàm này dùng để kiểm tra số lượng bit 11 của số xx là lẻ hay chẵn. Hàm sẽ trả về TRUE (1)\text{TRUE} \ (1) nếu như số lượng bit 11 của xx là lẻ, ngược lại trả về FALSE (0)\text{FALSE} \ (0)

Độ phức tạp: O(log2x)O(\log_2 x).

Ví dụ

#include <iostream>

using namespace std;

main()
{
    int n = 7; // 7 = 0111.
    cout << __builtin_parity(n);
	
    return 0;
}

Output

1

Hàm __builtin_clz(x)

Hàm này dùng để đếm số lượng bit 00 liên tiếp đứng trước bit 11 đầu tiên của số xx tính từ trái qua phải. Lưu ý, số lượng bit 00 sẽ phụ thuộc vào kiểu dữ liệu của số x,x, ví dụ số kiểu int sẽ có dạng 3232 bit, kiểu long long sẽ có dạng 6464 bit.

Lưu ý rằng, hàm này chỉ có thể sử dụng với các số nguyên không dấu có kiểu int. Các bạn có thể sử dụng hàm __builtin_clzl() cho kiểu dữ liệu long__builtin_clzll() cho kiểu dữ liệu long long theo cách hoàn toàn tương tự. Ngoài ra, nếu tham số đầu vào của hai hàm này là 00 thì giá trị trả về sẽ là undefined.

Độ phức tạp: O(log2x)O(\log_2 x).

Ví dụ

#include <iostream>

using namespace std;

main()
{
    int n = 16; // 16 = 00000000 00000000 00000000 00010000.
    cout << "Count of leading zeros before the first bit 1 of " << n << " is " << __builtin_clz(n);
	
    return 0;
}

Output

Count of leading zeros before the first bit 1 of 16 is 27

Hàm __builtin_ctz(x)

Ngược lại với hàm __builtin_clz(), hàm này sử dụng để đếm số lượng bit 00 liên tiếp đứng sau bit 11 cuối cùng của số x,x, theo chiều từ phải qua trái. Hoàn toàn tương tự ta có các hàm __builtin_ctzl()__builtin_ctzll() dành cho các kiểu dữ liệu longlong long.

Lưu ý đặc biệt cho hàm này vẫn giống như hàm __builtin_clz() - sẽ trả về undefined nếu như tham số đầu vào bằng 0,0, ngoài ra không hoạt động với số nguyên có dấu.

Độ phức tạp: O(log2x)O(\log_2 x).

Ví dụ

#include <iostream>

using namespace std;

main()
{
    int n = 16; // 16 = 00000000 00000000 00000000 00010000.
    cout << "Count of trailing zeros after the last bit 1 of " << n << " is " << __builtin_clz(n);
	
    return 0;
}

Output

Count of trailing zeros after the last bit 1 of 16 is 4

2. Các kĩ thuật thú vị với thao tác bit

Áp dụng các thao tác xử lý bit, ta có thể thực hiện được khá nhiều trick thú vị và đẩy nhanh được tốc độ thuật toán, tuy nhiên không phải trick nào cũng có ứng dụng thực tế (đôi khi chỉ để chém gió cho vui). Người viết sẽ liệt kê ra một số trick hay dưới đây, bạn đọc có thể tùy ý lựa chọn sử dụng trong các bài tập cụ thể nếu cảm thấy có tác dụng!

2.1. Kiểm tra một số bất kì có phải lũy thừa của 2 không?

Xét một số nguyên không âm n,n, nếu như nó là lũy thừa của 22 thì giá trị AND của nnn1n - 1 sẽ bằng 00. Tuy nhiên, công thức này không hoạt động nếu như n=0,n = 0, vì thế các bạn cần kiểm tra thêm cả điều kiện n0n \ne 0.

bool is_power2(int n)
{
    return n != 0 && (!(n & (n - 1)));
}

Độ phức tạp: O(1)O(1).

2.2. Đếm số lượng số xx nhỏ hơn hoặc bằng nn thỏa mãn n+x=nxn + x = n^x

Số lượng giá trị xx nói trên có thể đếm nhanh bằng một công thức:

res=2mres = 2^m

với mm là số lượng bit 00 của số nn

Chú ý rằng, giá trị mm này được đếm dựa theo việc biểu diễn nn ở hệ nhị phân và loại bỏ đi các bit 00 vô nghĩa ở phía tay phải.

int count_values(int n)
{
    int zero_bits = 0;
    while (n)
    {
        // Nếu n chẵn thì sẽ thu được một bit 0.
        // Công thức (n & 1) == 0 sẽ kiểm tra n có phải số chẵn không.
        zero_bits += ((n & 1) == 0);
        n >>= 1;
    }
	
    return 1 << zero_bits;
}

Độ phức tạp: O(1)\approx O(1).

2.3. Duyệt mọi tập con của tập hợp

Với một tập hợp AA gồm nn phần tử, áp dụng thao tác bit chúng ta có thể nhanh chóng duyệt qua mọi tập con của nó (tốc độ thuật toán sẽ nhanh hơn đáng kể so với việc sử dụng quay lui với các lời gọi đệ quy). Ta sẽ sử dụng một dãy bit gồm nn phần tử đại diện cho các trạng thái lựa chọn của tập hợp A,A, thì giá trị thập phân của các dãy bit đó sẽ nằm trong đoạn [0,2n1][0, 2^n - 1]. Khi đó, ta sẽ duyệt qua mọi số nguyên từ 00 tới 2n12^n - 1 và sử dụng mỗi số nguyên đó đại diện cho một cách lựa chọn tập con.

Khung thuật toán có thể mô tả sơ lược như sau

vector < int > a(n); // Tập hợp A gồm n phần tử.

// Xét tất cả các trạng thái tập con.
for (int mask = 0; mask < (1 << n); ++mask)
{
    // Xét từng phần tử của tập xem phần tử nào được chọn.
    // Phần tử i được chọn thì mask & (1 << i) = 1.
    for (int i = 0; i < n; ++i)
        if (mask & (1 << i))
        {
            // Ghi nhận phần tử a[i] vào tập con hiện tại.
            // Xử lý tùy ý tiếp theo.
        }
}

Với cách làm này, nếu như BB là tập con của AA thì số nguyên đại diện cho BB cũng sẽ luôn nhỏ hơn số nguyên đại diện cho A,A, rất thuận lợi cho việc kết hợp với quy hoạch động. Kĩ thuật này cũng là kĩ thuật được sử dụng khá thường xuyên trong các bài toán áp dụng Duyệt phân đôi tập hợp (Meet in the middle), hoặc trong các bài toán về bao hàm - loại trừ. Chúng ta sẽ phân tích kĩ hơn về nó ở phần bài tập minh họa phía sau.

3. Sử dụng bitset trong C++

Trong STL C++ có một cấu trúc dữ liệu biểu diễn tập hợp các bit, có thể được sử dụng để hỗ trợ các thao tác xử lý bit rất tốt, đó là bitset.

Về bản chất, bitset giống như một mảng/vector kiểu logic, tức là nó gồm các phần tử chỉ mang giá trị 01,0 - 1, tuy nhiên nó được cài đặt một cách tối ưu sao cho mỗi phần tử chỉ chiếm đúng một bit. Vì thế, không gian lưu trữ của một bitset sẽ nhỏ hơn so với một mảng/vector kiểu bool. Các thao tác trên bitset cũng nhanh hơn so với mảng/vector tới 6464 lần.

Khai báo bitset

Để khai báo một bitset, ta sử dụng thư viện <bitset> và khai báo theo cú pháp dưới đây:

#include <bitset>

using namespace std;

bitset < size > {name}(intialization);

Trong đó:

  • Tham số size thể hiện kích thước của bitset, tham số này bắt buộc phải có khi khai báo một bitset. Đây cũng là nhược điểm của bitset - kích thước phải cố định trước.
  • Tham số name thể hiện tên của bitset.
  • Tham số intialization thể hiện khởi tạo giá trị ban đầu của bitset. Có 3 cách để khởi tạo:
    • Không khởi tạo: Với cách này, bitset sẽ mặc định toàn bit 00.

      bitset < 8 > unintialized_bitset; // 00000000.
      
    • Khởi tạo bằng số nguyên hệ thập phân: Với cách làm này, bitset sẽ được khởi tạo bằng với biểu diễn nhị phân của số truyền vào.

      bitset < 8 > decimal_bitset(15); // 00001111	
      
    • Khởi tạo bằng xâu nhị phân: Với cách làm này, bitset sẽ được khởi tạo giá trị bằng với xâu nhị phân truyền vào. Tuy nhiên, xâu truyền vào không được phép có độ dài lớn hơn kích thước của bitset.

      bitset < 8 > string_bitset(string("1111")); // 00001111.
      // Hoặc bitset < 8 > string_bitset("1111");
      

Truy cập các bit của bitset

Container bitset là một cấu trúc dữ liệu rất đặc biệt, nó vừa giống xâu kí tự lại vừa giống mảng. Giống xâu ở chỗ, nó có thể được khởi tạo từ một xâu nhị phân, và in ra cả dãy bit trực tiếp thông qua câu lệnh cout (chứ không cần for qua từng phần tử rồi in), nhưng lại giống mảng ở chỗ cũng truy cập được vào từng phần tử thông qua toán tử []. Tuy nhiên, các bit trong bitset lại được đánh số thứ tự từ phải qua trái (giống với quy tắc đánh số bit trong hệ nhị phân), bắt đầu từ 00.

Cùng xem ví dụ dưới đây:

#include <iostream>
#include <bitset>

using namespace std;

main()
{
    bitset < 8 > sample_bitset("00001111");
    cout << "Bit at position 4 of sample_bitset is " << sample_bitset[4];
	
    return 0;
}

Kết quả đoạn code trên sẽ là

Bit at position 4 of sample_bitset is 0

Một số hàm thành viên của bitset

Container bitset có sẵn một số hàm thành viên, với tác dụng cụ thể như bảng dưới đây:

Cùng xem ví dụ dưới đây để hiểu cách hoạt động của các hàm trên:

#include <bitset>
#include <iostream>

using namespace std;

int main()
{
    // Declaring index variable.
    int index = 0;

    // Declaring a few bitset objects.
    bitset < 4 > all_set("1111"), all_unset;

    cout << "any() value: " << boolalpha << allSet.any() << endl;
    
    cout << "all() value: " << all_set.all() << endl;
    
    cout << "none() value: " << all_set.none() << endl;
    
    cout << "test() at index 0: " << noboolalpha << all_set.test(index) << endl;
    
    cout << "size() value: " << all_set.size() << endl;
    
    cout << "Value of all_unset on before using set(): " << all_unset << endl;
	
    all_unset.set(index);
    cout << "Value of all_unset on after using set(): " << all_unset << endl;

    cout << "Value of all_set on before using reset(): " << all_set << endl;
	
    all_set.reset(index);
    cout << "Value of all_set on after using reset(): " << all_set << endl;

    // Declaring an empty string.
    string bitString;
    // using to_string() method to assing value to empty string
    bit_string = all_set.to_string();
    cout << "bit_string: " << bit_string << endl;

    cout << "Unsigned Long value: " << all_set.to_ulong();

    return 0;
}

Kết quả chương trình trên sẽ là:

any() value: true
all() value: true
none() value: false
test() at index 0: 1
size() value: 4
Value of all_unset on before using set(): 0000
Value of all_unset on after using set(): 0001
Value of all_set on before using reset(): 1111
Value of all_set on after using reset(): 1110
bit_string: 1110
Unsigned Long value: 14

Các toán tử với bitset

Vì là một cấu trúc dữ liệu đặc trưng cho các bit nhị phân, nên các toán tử bitwise trong C++ được nạp chồng cho cả bitset. Như vậy, tất cả các toán tử &, |, !, <<=, >>=, &=, |=, ^=, ~ đều có thể sử dụng được trên bitset với ý nghĩa giống hệt như khi thao tác với kiểu số. Cùng xem ví dụ dưới đây:

// C++ program to show the different operator functions on
// bitset
#include <bitset>
#include <iostream>

using namespace std;

int main()
{
    bitset < 4 > bitset1("1001"), bitset2("1010");
    bitset < 4 > result;

    cout << "bitset1: " << bitset1 << "\nbitset2: " << bitset2 << endl;

    cout << "Accessing bit value at index 1 of bitset1: " << bitset1[1] << endl;

    // Bitwise AND.
    cout << "Bitwise AND using &: " << (result = bitset1 & bitset2) << endl;
    cout << "Bitwise AND using &=: " << (bitset1 &= bitset2) << endl;

    // Bitwise OR.
    bitset1 = 9; // 9 = 1001.
    cout << "Bitwise OR using &: " << (result = bitset1 | bitset2) << endl;
    cout << "Bitwise OR using &=: " << (bitset1 |= bitset2) << endl;

	// Bitwise NOT.
    cout << "Bitwise NOT: " << (result = ~bitset1) << endl;

    // Bitwise XOR.
    bitset1 = 9;
    cout << "Bitwise XOR: " << (bitset1 ^= bitset2) << endl;

    bitset1 = 9;
    cout << "Binary leftshift on bitwise1: " << (bitset1 <<= 1) << endl;
	
    bitset1 = 9;
    cout << "Binary rightshift on bitwise1: " << (bitset1 >>= 1) << endl;

    return 0;
}

Kết quả đoạn chương trình trên như sau:

Bitset1: 1001
Bitset2: 1010
Accessing bit value at index 1 of bitset1: 0
Bitwise AND using &: 1000
Bitwise AND using &=: 1000
Bitwise OR using &: 1011
Bitwise OR using &=: 1011
Bitwise NOT: 0100
Bitwise XOR: 0011
Binary leftshift on bitwise1: 0010
Binary rightshift on bitwise1: 0100

III. Bài tập minh họa

1. Nguyên tố cùng nhau

Đề bài

Cho trước một số nguyên dương nn. Ta đã biết phi hàm Euler của n,n, kí hiệu là ϕ(n)\phi(n) là số lượng số nguyên tố cùng nhau với nn và không vượt quá nn. Sau khi nghiên cứu được khái niệm này, An tỏ ra rất hứng thú và đã dễ dàng viết xong chương trình tính phi hàm Euler của nn. Tuy nhiên, không phải lúc nào chúng ta cũng cần xem xét trên cả đoạn số [1,n],[1, n], vì vậy An tự hỏi không biết có cách nào đếm số lượng số nguyên tố cùng nhau với nn trên đoạn [1,m][1, m] hay không?

Yêu cầu: Cho trước hai số nguyên nnm,m, hãy đếm số lượng số nguyên tố cùng nhau với nn trên đoạn [1,M]?[1, M]?

Input:

  • Một dòng duy nhất chứa hai số nguyên dương nnmm.

Ràng buộc:

  • 1mn10121 \le m \le n \le{10}^{12}.

Output:

  • Số nguyên duy nhất là kết quả bài toán.

Sample Input 1:

10 5

Sample Output 1:

2

Ý tưởng

Để đếm số phần tử nguyên tố cùng nhau với nn từ 11 tới r,r, ta có thể đếm phần bù: Lấy rr trừ đi số phần tử KHÔNG nguyên tố cùng nhau với nn từ 11 tới rr. Giả sử nn phân tích ra thừa số nguyên tố là: N=p1k1×p2k2××pnkn,N = p_1^{k_1} \times p_2^{k_2} \times \cdots \times p_n^{k_n}, thì các số KHÔNG nguyên tố cùng nhau với NN phải chia hết cho ít nhất một thừa số nguyên tố pip_i nào đó. Ta sẽ đếm số lượng này bằng cách xét các số chia hết cho pip_i trong đoạn [1,r][1, r] bằng công thức rpi\left\lfloor{\frac{r}{p_i}} \right\rfloor. Tuy nhiên, nếu chỉ đếm mỗi số lượng này thì sẽ bị thừa rất nhiều số, do có những số chia hết cho 22 số pi,p_i, cho 33 số $p_i...$Vì vậy ta áp dụng công thức bao hàm - loại trừ ở đây để tính. Công thức là:

(Caˊc soˆˊ chia heˆˊt cho 1 soˆˊ pi)(Caˊc soˆˊ chia heˆˊt cho 2 soˆˊ pi)+(Caˊc soˆˊ chia heˆˊt cho 3 soˆˊ pi)+\text{(Các số chia hết cho } 1 \text{ số } p_i) - \text{(Các số chia hết cho } 2 \text{ số } p_i) + \text{(Các số chia hết cho } 3 \text{ số } p_i) - \cdots +

Để sinh nhanh được các tập con của dãy số nguyên tố p,p, ta sử dụng kĩ thuật xử lý bit như đã đề cập ở mục II. Với mỗi tập con ta tính tích của chúng để tạo thành bội chung nhỏ nhất của số chia hết cho 1,2,3,...1, 2, 3,... số nguyên tố trong tập pp.

Độ phức tạp: O(n),O(\sqrt{n}), thời gian chạy chủ yếu lâu ở bước phân tích thừa số nguyên tố.

Code mẫu

#include <bits/stdc++.h>
#define int long long

using namespace std;

int N, M;

void enter()
{
    cin >> N >> M;
}

vector < int > extract(int N)
{
    vector < int > p;
    for (int i = 2; i * i <= N; ++i)
        if (N % i == 0)
        {
            p.push_back(i);

            while (N % i == 0)
                N /= i;
        }

    if (N > 1)
        p.push_back(N);

    return p;
}

void solution(int N, int M)
{
    vector < int > prime = extract(N);
    int K = prime.size();

    int inverse_path = 0; // Tính phần bù: Số lượng phần tử KHÔNG nguyên tố cùng nhau với N từ 1 tới r.
    for (int bitmask = 0; bitmask < (1 << K); ++bitmask) // Duyệt các trạng thái chọn tập con của tập hợp prime.
    {
        int group_count = 0, multi = 1; // Đếm số phần tử được chọn và tích các phần tử được chọn.
        for (int i = 0; i < K; ++i)
            if (bitmask & (1 << i)) // Phần tử i được chọn trong trạng thái hiện tại.
            {
                ++group_count;
                multi *= prime[i];
            }

        int cur_divisors = M / multi; // Số lượng số chia hết cho nhóm được chọn từ 1 tới r.
        if (group_count & 1) // Nếu nhóm này có số lượng lẻ -> bước cộng.
            inverse_path += cur_divisors;
        else // Nếu nhóm này có số lượng chẵn -> bước trừ.
            inverse_path -= cur_divisors;
    }

    cout << M - inverse_path; // Kết quả là r trừ đi phần bù.
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    enter();
    solution(N, M);

    return 0;
}

2. Sum Set

Đề bài

Cho dãy aa gồm nn phần tử nguyên dương.

Yêu cầu: Hãy đếm số tổng khác nhau có thể tạo ra từ các dãy con không nhất thiết liên tiếp của aa (không tính dãy rỗng)?

Input:

  • Dòng thứ nhất chứa số nguyên dương nn miêu tả số phần tử trong dãy.
  • Dòng thứ hai gồm nn phần tử miêu tả dãy aa.

Ràng buộc:

  • 1n10001 \le n \le 1000
  • 0<ai1000;i:1in0 < a_i \le 1000; \forall i: 1 \le i \le n.

Subtasks:

  • Subtask 11 (30%30\% số điểm): n20n \le 20.
  • Subtask 22 (40%40\% số điểm): n50n \le 50.
  • Subtask 33 (30%30\% số điểm): Không có ràng buộc gì thêm.

Output:

  • Gồm một số nguyên dương là kết quả bài toán.

Sample Input:

3
1 4 5

Sample Output:

6

Ý tưởng

Subtask 1

Sinh nhị phân bằng quay lui và dùng đếm phân phối để tính kết quả.

Độ phức tạp: O(2n)O(2^n).

Subtask 2

Sử dụng quy hoạch động cái túi, đặt f(i,j)f(i,j) là xét tới ii có thể tạo ra được tổng jj hay không.

Ta có:

  • f(0,0)=TRUEf(0,0) = \text{TRUE}.
  • f(i,j)=f(i1,j)f(i,j) = f(i-1,j) | f(i,jai)f(i,j-a_i).

Độ phức tạp: O(n×sum(ai))O\big(n \times sum(a_i)\big).

Subtask 3

Ta vẫn dùng quy hoạch động, nhưng cải tiến bằng bitset.

Đặt bitset < 1000001 > f[n], với bitset f[i]f[i] lưu những tổng có thể tạo ra được khi xét tới ii (là những bitbit 11).

Ban đầu tất cả bitset đều có toàn bit 0,0, riêng f[0][0]=1f[0][0] = 1.

Ta có f[i]=f[i1]f[i] = f[i-1] | (f[i1](f[i-1] << ai)a_i).

Phép toán f[i1]f[i-1] << aia_i có nghĩa là dịch bitset f[i1]f[i-1] đi aia_i bit, bởi nếu ta chọn cộng vào ai,a_i, thì ta sẽ tạo ra được các tổng mới từ f[i1]f[i-1] bằng cách thêm aia_i đơn vị. Do chúng ta đang lưu các tổng dưới dạng bit, nên đó chính là phép dịch aia_i bit.

Kết quả chính là số bit 11 của f[n]f[n] trừ đi 1,1, do ta không tính tập rỗng. Hay chính là f[n]f[n].count() 1- 1.

Độ phức tạp: O(n×sum(ai)64)O\left(n \times \frac{sum(a_i)}{64}\right), do các thao tác trên bitset nhanh gấp 6464 lần so với mảng.

Code mẫu

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+1;

void solution(int n, vector < int > &a) 
{
    bitset < maxn > f;
    for (int i = 0; i <= 1e6; ++i) 
        f[i] = 0;
    f[0] = true;
	
    for (int i = 1; i <= n; ++i) 
    {
        bitset < maxn > q = f;
        q <<= a[i];
        f |= q;
    } 

    cout << f.count() - 1<< endl;
}

main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
	
    vector < int > a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
		
    solution(n);
	
    return 0;
}

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.