Hiểu bài toán

Bài toán yêu cầu đếm số cách chia N học sinh thành K nhóm không rỗng, trong đó các nhóm được coi là không phân biệt (tức là thứ tự các nhóm không quan trọng). Đây chính là bài toán tìm số Stirling của loại thứ hai, thường ký hiệu là S(N, K). Với ràng buộc N, K ≤ 25, chúng ta có thể sử dụng quy hoạch động (Dynamic Programming) để tính toán trước hoặc theo từng test case.

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

Cách Quy hoạch động (Dynamic Programming)

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

long long dp[26][26];

void precompute() {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 1; i <= 25; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = (long long)j * dp[i - 1][j] + dp[i - 1][j - 1];
        }
    }
}

int main() {
    precompute();
    int T;
    cin >> T;
    while (T--) {
        int N, K;
        cin >> N >> K;
        if (K > N) cout << 0 << endl;
        else cout << dp[N][K] << endl;
    }
    return 0;
}

• Time Complexity: O(T + N*K) (với N, K <= 25)
• Space Complexity: O(N*K)

Công thức truy hồi cho số Stirling loại thứ hai là: S(n, k) = k * S(n-1, k) ÷ S(n-1, k-1). Ý nghĩa: Khi thêm phần tử thứ n vào:

1. Chọn 1 trong k nhóm hiện có để thêm phần tử n: có k * S(n-1, k) cách.
2. Tạo một nhóm mới chứa duy nhất phần tử n: có S(n-1, k-1) cách. Chúng ta xây dựng bảng DP từ dưới lên (từ 1 đến N) và lưu kết quả để sử dụng cho các test case sau đó.

Cách Quy hoạch động theo từng test case (Memoization)

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

unsigned long long dp[26][26] = {0};

unsigned long long dfs(int k, int n) {
    if (k == 1 || k == n) return 1;
    if (dp[k][n]) return dp[k][n];
    dp[k][n] = k * dfs(k, n - 1) + dfs(k - 1, n - 1);
    return dp[k][n];
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int k, n;
        cin >> n >> k;
        cout << dfs(k, n) << '\n';
    }
    return 0;
}

• Time Complexity: O(N*K) cho mỗi test case (trùng lặp được lưu)
• Space Complexity: O(N*K)

Cách tiếp cận này sử dụng đệ quy có nhớ (Memoization). Hàm dfs(k, n) trả về số cách chia n học sinh thành k nhóm. Nó áp dụng chính xác công thức truy hồi S(n, k) = k*S(n-1, k) + S(n-1, k-1). Bảng dp dùng để lưu các kết quả đã tính toán để tránh tính lại.

Cách Đệ quy không nhớ (Dùng cho hiểu biết)

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

long long stirling(int n, int k) {
    if (n == 0 && k == 0) return 1;
    if (n == 0 || k == 0) return 0;
    if (k == 1 || k == n) return 1;
    return k * stirling(n - 1, k) + stirling(n - 1, k - 1);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        cout << stirling(n, k) << endl;
    }
    return 0;
}

• Time Complexity: O(2^N)
• Space Complexity: O(N)

Đây là cách cài đặt trực tiếp công thức truy hồi mà không sử dụng bảng nhớ. Mặc dù ngắn gọn và dễ hiểu, nó rất chậm do tính toán lại các giá trị nhiều lần. Với N=25, độ phức tạp là quá lớn để chạy trong thời gian cho phép. Đây chỉ nên dùng để kiểm tra tính đúng đắn của công thức hoặc với N rất nhỏ.

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

Bài học kinh nghiệm

• Bài toán này tương đương với việc tính số Stirling của loại thứ hai (Stirling numbers of the second kind).
• Công thức truy hồi: S(n, k) = k * S(n-1, k) + S(n-1, k-1).
• Vì N, K nhỏ (≤ 25), giải pháp tối ưu nhất là quy hoạch động.

Lỗi thường gặp

• Lưu ý thứ tự tham số trong mảng 2 chiều dp[n][k] (hoặc dp[k][n] tùy biến thể), phải nhất quán với công thức truy hồi.
• Với N=25, số lượng cách chia có thể lớn hơn 2^64 (unsigned long long), nhưng thực tế S(25, 12) ≈ 1.510^18 vẫn nằm trong giới hạn của unsigned long long (không quá 1.810^19). Tuy nhiên, nếu N lớn hơn một chút, cần dùng số nguyên lớn (BigInt).
• Nếu K > N, đáp án phải là 0 (vì không thể chia N phần tử thành K nhóm không rỗng nếu K > N).