Phân tích thuật toán

Tóm tắt Bài toán

• Cho N số nguyên.
• Có T truy vấn, mỗi truy vấn cho số K.
• Với mỗi K, yêu cầu đếm số cách chọn K phần tử từ các nhóm số giống nhau trong mảng, rồi in ra kết quả dưới dạng modulo 10^9 + 7.

Ý tưởng chính

1. Đếm tần suất xuất hiện:

   • Đếm số lần xuất hiện của mỗi số trong mảng (freq).
   • Đếm số nhóm có cùng tần suất xuất hiện (cnt_map).

2. Chuẩn bị tổ hợp (Combination):

   • Để tính nhanh số tổ hợp ~ C(n, k) = \frac{n!}{k!(n-k)!} ~, ta cần:
     • Giai thừa (fact[]).
     • Giai thừa nghịch đảo (inv_fact[]), tính bằng phương pháp Lũy thừa nhanh (Fast Exponentiation) và Định lý Fermat nhỏ.
     • ~ a^{-1} \equiv a^{MOD-2} \pmod{MOD} ~ nếu MOD là số nguyên tố.

3. Xử lý từng truy vấn:

   • Với mỗi K, duyệt qua mảng tần suất (freq):
     • Nếu tần suất xuất hiện cnt ≥ K, thì có thể chọn K phần tử từ nhóm này.
     • Cộng dồn số cách chọn vào kết quả.

Độ phức tạp

• Thời gian:

  • precompute():
  • Tính giai thừa và giai thừa nghịch đảo: ~ O(MAX) ~
  • Đọc mảng và đếm tần suất: ~ O(N) ~
  • Xử lý mỗi truy vấn:
  • Duyệt qua các nhóm: ~ O(U) ~, với U là số lượng nhóm tần suất khác nhau.
  • Tính tổ hợp: ~ O(1) ~ nhờ precompute.
  • Tổng: ~ O(T \cdot U) ~
  • Tổng thời gian: ~ O(MAX + N + T \cdot U) ~

• Bộ nhớ:

  • Mảng fact và inv_fact: ~ O(MAX) ~
  • freq và cnt_map: ~ O(N) ~

Chương trình minh hoạ

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

const int MOD = 1e9 + 7;  // MOD để lấy phần dư
const int MAX = 1e6 + 5;  // Giới hạn tối đa cho giai thừa

vector<long long> fact(MAX);       // Mảng lưu giai thừa
vector<long long> inv_fact(MAX);   // Mảng lưu giai thừa nghịch đảo

// Hàm lũy thừa nhanh (Binary Exponentiation)
long long pow_mod(long long a, long long b) {
    long long res = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1) 
            res = res * a % MOD;   // Nếu b lẻ thì nhân thêm a vào kết quả
        a = a * a % MOD;           // Bình phương cơ số
        b >>= 1;                  // Chia đôi số mũ
    }
    return res;
}

// Tiền xử lý giai thừa và giai thừa nghịch đảo
void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAX; ++i) {
        fact[i] = fact[i-1] * i % MOD;  // Tính giai thừa
    }
    inv_fact[MAX-1] = pow_mod(fact[MAX-1], MOD-2); // Giai thừa nghịch đảo của MAX-1
    for (int i = MAX-2; i >= 0; --i) {
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
    }
}

// Hàm tính tổ hợp C(n, k)
long long comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

int main() {
    ios::sync_with_stdio(false);  // Tăng tốc độ đọc/ghi
    cin.tie(0);

    // Đọc từ file và ghi ra file
  //  freopen("EQUAL.inp", "r", stdin);
  //  freopen("EQUAL.out", "w", stdout);

    // Tiền xử lý giai thừa và giai thừa nghịch đảo
    precompute();

    int N, T;
    cin >> N >> T;

    // Đếm tần suất xuất hiện của từng số
    unordered_map<int, int> freq;
    for (int i = 0; i < N; ++i) {
        int x;
        cin >> x;
        freq[x]++;
    }

    // Xử lý từng truy vấn
    while (T--) {
        int K;
        cin >> K;
        long long res = 0;

        // Duyệt qua tất cả các tần suất trong freq
        for (auto &p : freq) {
            int cnt = p.second;  // Số lần xuất hiện của một số
            if (cnt >= K) {
                res = (res + comb(cnt, K)) % MOD;
            }
        }
        cout << res << '\n';
    }

    return 0;
}

Giải thích các thành phần quan trọng

1. Lũy thừa nhanh pow_mod()

• Tính ~ a^b \mod MOD ~ bằng Binary Exponentiation.
• Độ phức tạp: ~ O(\log b) ~.

2. Tiền xử lý giai thừa và giai thừa nghịch đảo precompute()

• Tính:
  • fact[i] = i! % MOD
  • inv_fact[i] = (i!)^{-1} % MOD bằng cách sử dụng Fermat's Little Theorem.
  • Độ phức tạp: ~ O(MAX) ~

3. Hàm comb(n, k)

• Tính số tổ hợp ~ C(n, k) = \frac{n!}{k!(n-k)!} \mod MOD ~ bằng: ~ C(n, k) = fact[n] \times inv\_fact[k] \times inv\_fact[n-k] \mod MOD ~
• Độ phức tạp: ~ O(1) ~

4. Xử lý truy vấn

• Với mỗi K, duyệt qua các nhóm tần suất:
  • Nếu cnt >= K, cộng số cách chọn vào kết quả.
• Độ phức tạp: ~ O(T \cdot U) ~

Ưu điểm của thuật toán

• Tính tổ hợp nhanh bằng cách tiền xử lý giai thừa và giai thừa nghịch đảo.
• Tối ưu truy vấn bằng cách sử dụng unordered_map để đếm tần suất và số nhóm.

Nhược điểm

• Sử dụng bộ nhớ lớn cho fact và inv_fact.
• Phức tạp hơn trong việc cài đặt và bảo trì.