Hiểu bài toán

Đếm số cách đặt k quân xe trên bàn cờ n x n sao cho không có hai quân nào nằm trên cùng một hàng hoặc cùng một cột. Vấn đề này tương đương với việc chọn k hàng và k cột khác nhau, sau đó đặt k quân xe tại giao điểm của các hàng và cột đã chọn sao cho mỗi hàng và mỗi cột chỉ có đúng một quân xe. Số cách sắp xếp k quân xe vào k vị trí giao điểm này là k! (k giai thừa). Do đó, tổng số cách là C(n, k) * k!.

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

Cách Sử dụng big number (BigInt)

// LonggVu.
#include<bits/stdc++.h>
using namespace std;
// Noob C++
void End(){
    cerr << "=> Thời gian code chạy: ";
    cerr << (1.0 * clock() / CLOCKS_PER_SEC) << " giây" << string(27, '\t');
}
#define LonggVu() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define use(x) freopen(x".inp", "r", stdin); freopen(x".out", "w", stdout);
#define fix(x) fixed << setprecision(x)
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define ms(a, x) memset(a, x, sizeof(a))
#define tc() int TC; cin >> TC; while(TC--)
#define el '\n'
#define fi first
#define se second
#define pb push_back
using ll = long long;
using ld = long double;
using str = string;

str tich(str a, str b){
    if(a == "0" || b == "0"){
        return "0";
    }
    str res = "";
    int n = a.size() - 1, m = b.size() - 1, nho = 0;
    for(int i=0; i<=m+n || nho; i++){
        for(int j=max(0, i-m); j<=min(i, n); j++){
            nho += (a[n-j] - '0') * (b[m-i+j] - '0');
        }
        res += nho%10 + '0';
        nho /= 10;
    }
    reverse(res.begin(), res.end());
    return res;
}
str chia(str a, int b){
    if(a == "0") return "0";
    str res = "";
    int nho = 0;
    for(char x : a){
        nho = nho * 10 + (x - '0');
        res += (nho / b) + '0';
        nho %= b;
    }
    int i = 0;
    while(res[i] == '0') i++;
    return res.substr(i);
}
str add(str a, str b){
    if(a == "0") return b;
    if(b == "0") return a;
    str res = "";
    int i = a.size() - 1, j = b.size() - 1, nho = 0;
    while(i >= 0 || j >= 0 || nho){
        int sum = nho;
        if(i >= 0) sum += a[i--] - '0';
        if(j >= 0) sum += b[j--] - '0';
        res += (sum % 10) + '0';
        nho = sum / 10;
    }
    reverse(res.begin(), res.end());
    return res;
}
string C(int n, int k) {
    if (k > n - k) k = n - k;
    string res = "1";
    for (int i = 1; i <= k; i++) {
        res = tich(res, to_string(n - i + 1));
        res = chia(res, i);
    }
    return res;
}
string factorial(int n) {
    if (n == 0) return "1";
    string res = "1";
    for (int i = 1; i <= n; i++) {
        res = tich(res, to_string(i));
    }
    return res;
}
int main() {
    LonggVu()
    int k, n;
    cin >> k >> n;
    if (k == 0) {
        cout << 1 << endl;
        return 0;
    }
    string c = C(n, k);
    string f = factorial(k);
    cout << tich(c, f) << endl;
    return 0;
}

• Time Complexity: O(k^2 * log(k!)) hoặc O(k * log(k!) * L)
• Space Complexity: O(L)

Đây là cách tiếp cận tổng quát nhất, giải quyết bài toán cho mọi giá trị đầu vào bằng cách tự cài đặt các phép toán số học trên chuỗi ký tự (Big Integer). Hàm tich thực hiện nhân hai số lớn, chia thực hiện chia số lớn cho số nguyên, add cộng hai số lớn. Hàm C(n, k) tính kết hợp bằng cách nhân dãy (n-k+1) đến n rồi chia cho 1 đến k để tránh tràn số. Hàm factorial(k) tính giai thừa. Phương pháp này không phụ thuộc vào giới hạn của kiểu dữ liệu cơ bản.

Cách Sử dụng unsigned long long (Tối ưu)

#include <iostream>
using namespace std;

int main() {
    int k, n;
    cin >> k >> n;
    unsigned long long ans = 1;
    // Tính P(n, k) = n! / (n-k)! bằng cách nhân dãy số từ n - k + 1 đến n
    // Sau đó chia dần cho 1 đến k để tính kết hợp
    // Cach 1: Nhan truoc, chia sau (co the bi overflow neu n lon)
    // Cach 2: Giai thua k, tinh C(n,k) = P(n,k) / k!

    // Cach 3: Tinh C(n, k) bang cong thuc Pascal hoac nhan chia dan
    // Cach nay an toan hon ve mat so sanh

    for (int i = 1; i <= k; ++i) {
        ans = ans * (n - i + 1) / i;
    }

    // Tinh k! va nhan vao
    unsigned long long fact_k = 1;
    for (int i = 2; i <= k; ++i) fact_k *= i;

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

• Time Complexity: O(k)
• Space Complexity: O(1)

Giải pháp này dựa trên nhận thức rằng kết quả bài toán chính là số cách chọn k hàng và k cột rồi sắp xếp chúng, tức là C(n, k) * k!. Ta có thể tính C(n, k) bằng công thức truy hồi Pascal hoặc công thức nhân chia: C(n, k) = (n/1) * ((n-1)/2) * ... * ((n-k+1)/k). Để tránh số quá lớn, ta thực hiện phép chia ngay khi có thể. Ví dụ: ans = ans * (n - i + 1) / i. Do ans luôn là số nguyên nên phép chia này sẽ không dư số. Sau khi có C(n, k), ta nhân với k! (tính bằng vòng lặp). Với n <= 100, kết quả hoàn toàn nằm trong phạm vi unsigned long long (khoảng 1.8 x 10^19).

Cách Công thức biến đổi toán học

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int k, n;
    cin >> k >> n;
    // Cong thuc: C(n, k) * k! = n! / (n - k)!
    // Tinh P(n, k) = n * (n-1) * ... * (n - k + 1)
    unsigned long long ans = 1;
    for (int i = 0; i < k; i++) {
        ans *= (n - i);
    }
    cout << ans << endl;
    return 0;
}

• Time Complexity: O(k)
• Space Complexity: O(1)

Đây là cách tiếp cận ngắn gọn nhất. C(n, k) * k! = (n! / (k! * (n-k)!)) * k! = n! / (n-k)!. Đây chính là công thức hoán vị (Permutation) P(n, k) hoặc nPr. Ta chỉ cần nhân các số từ n về ngược lại n-k+1. Ví dụ: n=2, k=2 -> 2 * 1 = 2. N=3, k=2 -> 3 * 2 = 6. Vòng lặp chạy k lần.

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

Bài học kinh nghiệm

• Bài toán có thể được chia thành 2 bước: (1) Chọn k hàng và k cột để đặt xe (không trùng lặp). Số cách chọn k hàng là C(n, k), chọn k cột là C(n, k). (2) Sắp xếp k quân xe vào các giao điểm sao cho mỗi hàng/cột chỉ có 1 quân (tương đương hoán vị của k phần tử), có k! cách.
• Tổng số cách là C(n, k) * C(n, k) * k! = (C(n, k))^2 * k!.
• Quy luật bài toán là hoán vị có điều kiện: Chọn k vị trí trên bàn cờ sao cho không có 2 vị trí nào cùng hàng hoặc cùng cột. Số cách chọn k cột trong n cột là C(n, k). Sau đó, ta có k hàng được đánh dấu và k cột được đánh dấu. Đặt xe vào hàng 1 tại 1 trong k cột, hàng 2 tại 1 trong k-1 cột còn lại... Tổng số cách là k!.
• Nhận thấy (C(n, k))^2 * k! = (n! / (k! * (n-k)!))^2 * k! = n! * n! / (k! * (n-k)! * (n-k)!). Tuy nhiên, cách tính hiệu quả nhất là kết hợp các phép tính: C(n, k) * k! = n! / (n-k)!. Do đó đáp án cuối cùng là (n! / (n-k)!) * C(n, k). Hay ngắn gọn hơn: P(n, k) * C(n, k).
• Một cách khác: Đặt xe lần lượt vào các hàng. האמר 1 có n cách, hàng 2 có n-1 cách... האמר k có n-k+1 cách. Tổng P(n, k). Sau đó ta cần chọn k hàng để đặt xe (C(n, k)). Kết quả là P(n, k) * C(n, k).

Lỗi thường gặp

• Tràn số (Overflow): Nếu dùng int hoặc long long thông thường, kết quả có thể vượt quá giới hạn cho phép (khoảng 10^18). Cần dùng unsigned long long hoặc Big Integer.
• Sai công thức: Nhầm lẫn giữa số cách chọn vị trí và số cách đặt xe. Ví dụ, chỉ tính C(n, k) * k! mà quên mất có C(n, k) cách để chọn các hàng (hoặc cột). Tuy nhiên, do tính đối xứng của hàng và cột, ta có thể tính P(n,k) * C(n,k) hoặc P(n,k) * P(n,k) / k!.
• Xử lý k=0: Mặc dù đề bài k>=1, nhưng các giải thuật Big Integer cần đảm bảo xử lý đúng nếu k=0 (kết quả là 1).