Hiểu bài toán

Bài toán yêu cầu đếm số cách chọn n độ khó khác nhau, trong đó độ khó của bài thứ i phải nằm trong đoạn [1, mi]. Để đảm bảo các độ khó khác nhau, ta cần chọn n số nguyên phân biệt. Nếu ta xét các ràng buộc theo thứ tự tăng dần của mi (sau khi sắp xếp), tại bước thứ i (tính từ 0), ta đã chọn xong i độ khó cho các bài trước đó. Do đó, tại bước này, ta cần chọn 1 độ khó mới từ tập [1, mi] sao cho nó khác với i độ khó đã chọn trước đó. Nếu mi <= i, không thể chọn thêm độ khó mới (vì chỉ có mi số trong [1, mi], và đã có i số phân biệt bị chiếm dụng). Nếu mi > i, số cách chọn là (mi - i). Kết quả cuối cùng là tích của các số cách chọn này cho tất cả các bài.

Các cách tiếp cận

Cách Tham lam (Sắp xếp và Tích)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const long long MOD = 1e9 + 7;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<long long> m(n);
    for (int i = 0; i < n; ++i) {
        cin >> m[i];
    }

    // Sắp xếp các ràng buộc độ khó tăng dần
    sort(m.begin(), m.end());

    long long ans = 1;
    for (int i = 0; i < n; ++i) {
        // Số lựa chọn tại bước i là m[i] - i
        long long choices = m[i] - i;

        // Nếu số lựa chọn <= 0, không có cách nào để chọn phân biệt
        if (choices <= 0) {
            ans = 0;
            break;
        }

        ans = (ans * choices) % MOD;
    }

    cout << ans << endl;
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Phương pháp này dựa trên nhận định tham lam: để tối đa hóa số cách chọn (hoặc chỉ để tồn tại một cách hợp lệ), ta nên xử lý các ràng buộc chặt chẽ nhất trước. Bằng cách sắp xếp mảng m theo thứ tự tăng dần, ta đảm bảo rằng tại bước i (từ 0 đến n-1), ta đang xét bài toán có giới hạn m_i lớn nhất có thể so với các bài đã xét.

Tại bước i:

• Đã có i độ khó được chọn cho các bài trước đó (từ 0 đến i-1).
• Các độ khó này nằm trong tập [1, mi] vì m được sắp xếp tăng dần (m{i-1} <= m_i).
• Để chọn độ khó cho bài thứ i, ta cần chọn một số nguyên phân biệt từ [1, m_i].
• Số lượng số nguyên dương trong [1, mi] là mi.
• Số lượng số đã bị chiếm dụng bởi các bài trước là i.
• Số cách chọn còn lại là m_i - i.

Nếu tại bất kỳ bước nào mi <= i, tức là số lượng số trong tập hợp [1, mi] ít hơn hoặc bằng số lượng số đã chọn (i), nên không thể chọn thêm số phân biệt. Khi đó kết quả là 0.

Tổng kết quả là tích lũy các phương án (m_i - i) cho tất cả các bước.

Cách Brute Force (Quay lui / Sinh tổ hợp)

// Pseudo-code for Brute Force approach
#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> m;
int count = 0;
bool used[1000005]; // Kích thước lớn, chỉ dùng cho min(m)

void try_solve(int idx) {
    if (idx == n) {
        count++;
        return;
    }
    for (int x = 1; x <= m[idx]; ++x) {
        if (!used[x]) {
            used[x] = true;
            try_solve(idx + 1);
            used[x] = false;
        }
    }
}

int main() {
    cin >> n;
    m.resize(n);
    int min_m = 1000001;
    for(int i=0; i<n; ++i) {
        cin >> m[i];
        if(m[i] < min_m) min_m = m[i];
    }
    // CẢNH BÁO: Độ phức tạp quá cao, chỉ mang tính lý thuyết
    // Nếu min_m = 10^6 và n = 10^5, số bước là P(10^6, 10^5) ~ 10^{500000}
    try_solve(0);
    cout << count;
    return 0;
}

• Time Complexity: O(P(max(m), n)) (Quá lớn, không khả thi)
• Space Complexity: O(max(m))

Đây là cách tiếp cận trực quan nhất: thử tất cả các tổ hợp độ khó có thể. Ta quay lui qua từng bài tập, thử mọi độ khó từ 1 đến m_i chưa được sử dụng. Nếu chọn được đủ n độ khó khác nhau, tăng biến đếm.

Tuy nhiên, số lượng tổ hợp có thể cực kỳ lớn. Ví dụ, nếu mi khoảng 10^5, số cách chọn là một số mũ rất lớn, vượt quá khả năng tính toán của máy tính. Do đó, phương pháp này chỉ phù hợp với các dữ liệu đầu vào rất nhỏ (n <= 10, mi <= 20). Với ràng buộc n <= 10^5, phương pháp này chắc chắn bị Time Limit Exceeded.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Việc sắp xếp các ràng buộc m_i theo thứ tự tăng dần là chìa khóa để biến bài toán phức tạp thành một bài toán tham lam đơn giản.
• Bài toán có thể được chia thành n giai đoạn độc lập sau khi sắp xếp: tại giai đoạn i, chỉ cần chọn 1 số phân biệt từ [1, mi], số lượng số phân biệt còn lại là (mi - i).

Lỗi thường gặp

• Quên sắp xếp mảng m trước khi tính toán, dẫn đến kết quả sai.
• Sử dụng biến đếm có kiểu dữ liệu quá nhỏ (ví dụ: int) gây tràn số (overflow), cần dùng long long và取模 (modular arithmetic) sau mỗi phép nhân.
• Xử lý sai trường hợp m[i] - i <= 0: phải kiểm tra nếu <= 0 thì kết quả là 0 và dừng ngay lập tức.