+4

Công thức Bao hàm - Loại trừ

I. Mở đầu

Công thức bao hàm - loại trừ là một công thức sử dụng để tính lực lượng (số lượng phần tử) của hợp của nhiều tập hợp. Công thức được phát biểu như sau: "Để tính lực lượng của hợp của nhiều tập hợp, ta tính tổng lực lượng các tập hợp đó, rồi trừ đi lực lượng của giao của các cặp hai tập hợp khác nhau, rồi cộng lực lượng của giao các bộ ba tập hợp khác nhau, rồi trừ đi lực lượng của các bộ bốn tập hợp, và cứ thế cho đến khi ta xét đến giao của tất cả các tập hợp."

Đối với các tập hợp, công thức có thể được viết ở dạng như sau: Giả sử có NN tập hợp A1,A2,A3,...,ANA_1, A_2, A_3,..., A_N. Lực lượng của hợp của NN tập hợp là:

Ta có thể minh họa công thức bằng một sơ đồ Venn trong trường hợp N=3N = 3 như sau:

Như sơ đồ, ta thấy lực lượng của ABCA \cap B \cap C bằng tổng lực lượng của A,B,CA, B, C trừ đi lực lượng của các giao AB,BC,CAA \cap B, B \cap C, C \cap A rồi cộng thêm lực lượng của ABCA \cap B \cap C:

image.png

Bằng phương pháp tương tự ta có thể minh họa được công thức với NN tập hợp.

Ví dụ: Đếm số lượng số từ 11 tới NN và không chia hết cho số nào trong tập {2,3,5}\{2, 3, 5\}:

Ta có thể biến đổi bài toán thành đếm phần bù: Đếm số lượng phần tử chia hết cho ít nhất một số trong tập {2,3,5}\{2, 3, 5\} rồi lấy NN trừ đi số lượng đó. Đặt AA là tập hợp các phần tử chia hết cho 2, B2,\ B là tập hợp các phần tử chia hết cho 3, C3, \ C là tập hợp các phần tử chia hết cho 55 từ 1 tới NN. Cần tính ABC|A \cup B \cup C|. Dựa vào công thức bao hàm, loại trừ, ta có:

image.png

Đoạn mã tính toán công thức trên có thể viết đơn giản như sau:

int count_numbers(int N)
{
    return N - N / 2 - N / 3 - N / 5 + N / (2 * 3) +
           N / (3 * 5) + N / (2 * 5) - N / (2 * 3 * 5);     
}

Công thức bao hàm - loại trừ có sức mạnh cực kì to lớn trong các bài toán đếm của toán học tổ hợp. Sau đây chúng ta sẽ cùng nghiên cứu một số bài toán ứng dụng của công thức này!

II. Bài toán ví dụ

1. Chính phương và Lập phương

Đề bài

Dãy số chính phương và lập phương là dãy gồm các số chính phương và lập phương. Sau đây là một vài số đầu tiên trong dãy: 1,4,8,9,16,1, 4, 8, 9, 16, \dots

Yêu cầu: Cho số nguyên dương nn. Hãy xác định trong đoạn [1;n][1; n] có bao nhiêu số nằm trong dãy số chính phương và lập phương.

Input:

  • Dòng đầu tiên chứa số nguyên tt — số lượng test case.
  • tt dòng tiếp theo tương ứng với tt test case, mỗi dòng chứa số nguyên nn.

Ràng buộc:

  • 1t201 \le t \le 20.
  • 1n1091 \le n \le 10^9.

Output:

  • Gồm tt dòng là kết quả tương ứng với tt test case.

Sample Input:

6
10
1
25
1000000000
999999999
500000000

Sample Output:

4
1
6
32591
32590
23125

Ý tưởng

Dãy số gồm các số chính phương sẽ là dãy gồm các số có dạng x2,x^2, với x1x \ge 1x2nx^2 \le n.

Tương tự, dãy số gồm các số lập phương sẽ là dãy gồm các số có dạng x3,x^3, với x1x \ge 1x3nx^3 \le n.

Tuy nhiên, trong hai dãy số đó sẽ có những số bị trùng nhau, tức là vừa là số chính phương, vừa là số lập phương. Các số đó có dạng x2×3=x6,x^{2 \times 3} = x^6, với x1x \ge 1x6nx^6 \le n. Ta sẽ tạo ra dãy AA gồm các số chính phương, dãy BB gồm các số lập phương và dãy CC gồm các số dạng lũy thừa bậc 66.

Gọi cnt1cnt_1 là số lượng số chính phương không vượt quá n,cnt2n, cnt_2 là số lượng số lập phương không vượt quá nncnt3cnt_3 là số lượng số vừa là chính phương vừa là lập phương không vượt quá nn. Ba giá trị này có thể dễ dàng tính ra được bằng cách tìm kiếm nhị phân trên ba mảng A,B,CA, B, C. Sau đó, theo công thức bao hàm loại trừ, số lượng số nằm trong dãy chính phương - lập phương từ 11 tới nn sẽ là:

cnt1+cnt2cnt3cnt_1 + cnt_2 - cnt_3

Để đẩy nhanh tốc độ giải thuật, ta sẽ khởi tạo trước ba mảng A,B,CA, B, C tới các số không vượt quá 109,10^9, rồi ứng với mỗi giá trị nn ở từng test case thì thực hiện tìm kiếm nhị phân và tính toán như công thức nói trên.

Độ phức tạp: O(t×sqrt(n))\approx O\big(t \times sqrt(n)\big).

Cài đặt

#include <bits/stdc++.h>

using namespace std;

vector < int > a, b, c;

void init()
{
    for (int i = 1; i * i <= 1e9; ++i) 
        a.push_back(i * i);
    for (int i = 1; i * i * i <= 1e9; ++i) 
        b.push_back(i * i * i);
    for (int i = 1; i * i * i * i * i * i <= 1e9; ++i)
        c.push_back(i * i * i * i * i * i);
}

void solve_testcase(int n)
{
    int cnt1 = (upper_bound(a.begin(), a.end(), n) - a.begin());
    int cnt2 = (upper_bound(b.begin(), b.end(), n) - b.begin());
    int cnt3 = (upper_bound(c.begin(), c.end(), n) - c.begin());
	
    cout << cnt1 + cnt2 - cnt3 << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
	
    init();
	
    int t; 
    cin >> t;
	
    while(t--) 
    {
        int n;
        cin >> n;
		
        solve_testcase(n);
    }
        
    return 0;
}

2. Ba - Năm - Bảy

Đề bài

Thầy giáo cho UcoderA định nghĩa về dãy số ba - năm - bảy như sau: Là một dãy số tăng dần, các phần tử của dãy chia hết cho ít nhất một trong ba số 33, 5577. Ví dụ một vài phần tử đầu tiên của dãy: {3;5;6;7;9;10;12;14;15;18;20;21;24;25;}\{3; 5; 6; 7; 9; 10; 12; 14; 15; 18; 20; 21; 24; 25; \dots\}

Yêu cầu: Cho số nguyên k,k, hãy xác định giá trị phần tử thứ kk của dãy số ba - năm - bảy?

Input:

  • Một dòng duy nhất chứa số nguyên kk.

Ràng buộc:

  • 1k10181 \le k \le 10^{18}.

Output:

  • Phần tử thứ kk của dãy số ba-năm-bảy.

Sample Input 1

13

Sample Output 1

24

Sample Input 2

100

Sample Output 2

185

Ý tưởng

Với các subtask nhỏ, ta có thể sử dụng vòng lặp sau đó tăng dần số xx đang xét cho đến khi đó là phần tử thứ kk ở trong dãy ba-năm-bảy.

Độ phức tạp thuật toán lúc này là O(n)O(n). Ta cần một thuật toán tốt hơn.

Để cải tiến cách làm, các bạn cần sử dụng chặt nhị phân và kiến thức về bao hàm bù trừ.

Với mỗi số x,x, ta có thể xác định được trước nó có bao nhiêu số chia hết cho 3,53, 5 hoặc 77 bằng cách sau:

Gọi số lượng số bé hơn hoặc bằng xx chia hết cho 33cnt[3]=x3cnt[3] = \left\lfloor\frac{x}{3}\right\rfloor, định nghĩa tương tự cho cnt[5]cnt[5]cnt[7]cnt[7]. Số lượng số chia hết cho cả 3355cnt[35]=cnt[15]=x15cnt[3\cdot5] = cnt[15] = \left\lfloor\frac{x}{15}\right\rfloor, định nghĩa tương tự cho cnt[37]=cnt[21]cnt[3\cdot7] = cnt[21]cnt[75]=cnt[35]cnt[7\cdot5] = cnt[35]. Số lượng số chia hết cho cả 33, 5577cnt[357]=cnt[105]cnt[3\cdot5\cdot7] = cnt[105].

Ta thấy rằng tổng cnt[3]+cnt[5]+cnt[7]cnt[3] + cnt[5] + cnt[7] sẽ bị trùng với nhau một lượng phần cnt[15]cnt[15], cnt[21]cnt[21]cnt[35]cnt[35] nên ta phải trừ đi lượng đấy, nhưng nếu trừ đi thì ta sẽ mất một lượng cnt[105]cnt[105] nên phải cộng bù vào. Vậy số lượng số chia hết cho 33, 55 hoặc 77 bé hơn hoặc bằng xx là:

cnt[3]+cnt[5]+cnt[7]cnt[15]cnt[21]cnt[35]+cnt[105]cnt[3] + cnt[5] + cnt[7] - cnt[15] - cnt[21] - cnt[35] + cnt[105]

Có được công thức trên, bạn đọc có thể sử dụng kĩ thuật chặt nhị phân tìm kết quả để tìm số xx bé nhất sao cho từ 33 đến xx có đúng kk số chia hết cho 33, 55 hoặc 77.

Độ phức tạp thuật toán: O(nlogn)O(n\log n).

Cài đặt

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
    ll k;
    cin >> k;
	
    ll l = 3, r = 2e18, ans;
    while(l <= r)
    {
        ll x = (l + r) / 2LL;

        ll cnt3 = x / 3LL;
        ll cnt5 = x / 5LL;
        ll cnt7 = x / 7LL;
        ll cnt15 = x / 15LL;
        ll cnt21 = x / 21LL;
        ll cnt35 = x / 35LL;
        ll cnt105 = x / 105LL;
		
        if (cnt3 + cnt7 + cnt5 - cnt15 - cnt21 - cnt35 + cnt105 >= k) 
            r = x - 1, ans = x;
        else 
            l = x + 1;
    }
	
    cout << ans;
	
    return 0;
}

3. Dãy chữ số đầy đủ

Đề bài

Cho trước số nguyên dương nn. Một dãy a1,a2,,aNa_1,a_2,\dots,a_N được gọi là dãy đầy đủ nếu thỏa mãn những điều sau đây:

  • 0ai90 \le a_i \le 9.
  • Tồn tại một vị trí ii nào đó sao cho ai=0a_i=0.
  • Tồn tại một vị trí ii nào đó sao cho ai=9a_i=9.

Yêu cầu: Hãy đếm số số dãy đẩy đủ có độ dài nn. Kết quả có thể rất lớn, hãy in ra số dư khi chia cho 109+710^9+7.

Input:

  • Dòng duy nhất chứa một số nn.

Constraints:

  • 1n1061 \le n \le 10^6.

Output:

  • Một số duy nhất là số dư của kết quả sau khi chia cho 109+710^9 + 7.

Sample Input 1:

2

Sample Output 1:

2

Giải thích:

22 dãy là (0,9)(0,9)(9,0)(9,0).

Ý tưởng

Có tổng cộng 10n10^n dãy AA độ dài nn0ai90\le a_i \le 9.

Thay vì đếm trực tiếp, ta sẽ sử dụng kĩ thuật đếm phần bù trong bài toán này. Cụ thể, ta sẽ trừ đi những dãy không phải là dãy đầy đủ, hay những dãy không tồn tại ai=0a_i=0 hoặc không tồn tại ai=9a_i=9. Số lượng đó như sau:

  • Có tổng cộng 9n9^n dãy AA không tồn tại ai=0a_i=0.
  • Có tổng cộng 9n9^n dãy AA không tồn tại ai=9a_i=9.
  • Có tổng cộng 8n8^n dãy AA không tồn tại ai=0a_i=0ai=9a_i=9.

Theo nguyên lí bao hàm - loại trừ, ta suy ra có 9n+9n8n9^n + 9^n - 8^n dãy AA không tồn tại ai=0a_i=0 hoặc không tồn tại ai=9a_i=9.

Như vậy đáp án là 10n(9n+9n8n)10^n - (9^n + 9^n - 8^n).

Độ phức tạp: O(n)O(n) hoặc O(log2(n))O\big(\log_2(n)\big) tùy vào cài đặt để tính các lũy thừa. Lưu ý kết quả có phép trừ, do đó nếu sử dụng ngôn ngữ C++ thì cần chú ý tránh để xảy ra trường hợp kết quả bị âm sau khi chia dư cho 109+710^9 + 7.

Cài đặt

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

using namespace std;

const int mod = 1e9 + 7;

int binary_exponentiation(int a, int b, int mod)
{
    if (b == 0)
        return 1LL;

    int half = binary_exponentiation(a, b / 2LL, mod) % mod;

    if (b & 1)
        return (((half * half) % mod) * (a % mod)) % mod;
    else 
        return (half * half) % mod;
}

main()
{
    int n;
    cin >> n;

    int x = binary_exponentiation(10, n, mod);
    int y = (2 * binary_exponentiation(9, n, mod) % mod - binary_exponentiation(8, n, mod) + mod) % mod;

    cout << (x - y + mod) % mod;

    return 0;
}

III. Tài liệu tham khảo


©️ Tác giả: Vũ Quế Lâm từ Viblo


All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí