Hiểu bài toán

Cho hai số nguyên không âm a và b (hoặc n và m). Đếm số cách chọn 3 chữ số từ a chữ số '0' và b chữ số '1' (hoặc ngược lại) để tạo thành một xâu đối xứng. Xâu đối xứng ở đây được hiểu là một xâu có thể đọc được từ trái sang phải và từ phải sang trái như nhau. Ví dụ: '010', '111', '000' là hợp lệ. '011' không hợp lệ. Bài toán yêu cầu tính toán số lượng cách sắp xếp này, không phân biệt các vị trí ban đầu mà chỉ quan tâm đến số lượng '0' và '1' có sẵn.

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

Cách Công thức tổ hợp trực tiếp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
ll ch(ll k, ll x) {
    ll gt = 1;
    for (int i = x - k + 1; i <= x; i++) {
        gt *= i;
    }
    return gt;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("PALIN3.inp", "r", stdin);
    freopen("PALIN3.out", "w", stdout);
    cin >> n >> m;
    ll ans = 0;
    if (n >= 3) ans += ch(3, n);
    if (m >= 3) ans += ch(3, m);
    if (m >= 2 && n >= 1) ans += ch(2, m) * n;
    if (n >= 2 && m >= 1) ans += ch(2, n) * m;
    cout << ans;
    return 0;
}

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

Phương pháp này phân tích các trường hợp tạo xâu đối xứng độ dài 3 dựa trên số lượng '0' (n) và '1' (m) có sẵn.

• Xâu '000' (hoặc '111'): Chọn 3 ký tự giống nhau. Số cách là C(n, 3) nếu dùng '0', hoặc C(m, 3) nếu dùng '1'.
• Xâu '010' (hoặc '101'): Xâu có ký tự ở đầu và cuối giống nhau, ở giữa khác. Ví dụ '010' cần 2 chữ số '0' và 1 chữ số '1'. Số cách là C(n, 2) * m (chọn 2 '0' từ n, 1 '1' từ m). Tổng hợp lại, ta có: ans = C(n, 3) + C(m, 3) + C(n, 2) * m + C(m, 2) * n. Hàm ch(k, x) tính giá trị P(n, k) = n * (n-1) * ... * (n-k+1) thay vì chọn tổ hợp C(n, k) để tránh chia số lớn. Tuy nhiên, công thức này chỉ hợp lệ khi ta quan tâm đến cách chọn các vị trí chứ không phải số lượng xâu distintinct. Nếu bài toán yêu cầu số lượng xâu distinct thì cần chia thêm阶乘. Dựa vào code và output thường là số lớn, cách này tính số cách chọn 3 vị trí trong bộ nhớ.

Cách Brute Force (Lặp qua tất cả xâu)

// Pseudocode approach
long long count = 0;
for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
        for (int k = 0; k < 2; k++) {
            if (i == k) { // Xâu đối xứng
                int cnt0 = (i == 0) + (j == 0) + (k == 0);
                int cnt1 = (i == 1) + (j == 1) + (k == 1);
                if (cnt0 <= n && cnt1 <= m) {
                    // Tính số cách sắp xếp các ký tự này (nếu distinct)
                    // Hoặc cộng dồn (nếu đếm số cách chọn vị trí)
                    count += ...;
                }
            }
        }
    }
}

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

Vì độ dài xâu chỉ là 3, ta có thể liệt kê các xâu đối xứng có thể: '000', '111', '010', '101'.

• '000': Cần n >= 3.
• '111': Cần m >= 3.
• '010': Cần n >= 2, m >= 1.
• '101': Cần n >= 1, m >= 2. Đây là cách tiếp cận thô (Brute Force) logic cho bài toán này, nhưng do độ dài cố định nên nó trở thành công thức toán học. Nó giúp kiểm tra lại tính đúng đắn của phương pháp công thức.

Cách Công thức tối ưu hóa biến đổi

#include <bits/stdc++.h>
using namespace std;
long long n, a, b, i, j;
int main() {
    if (fopen("PALIN3.inp", "r")) {
        freopen("PALIN3.inp", "r", stdin);
        freopen("PALIN3.out", "w", stdout);
    }
    cin >> a >> b;
    i = a * (a - 1) * (a - 2) + b * (b - 1) * (b - 2) + a * (a - 1) * b + b * (b - 1) * a;
    cout << i;
}

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

Đây là phiên bản trực tiếp của phương pháp 1, nhưng được viết ra dưới dạng công thức nhân tử số học để tối ưu tốc độ nhập xuất và tính toán. Công thức: i = a(a-1)(a-2) + b(b-1)(b-2) + a(a-1)b + b(b-1)a. Phân tích:

• a(a-1)(a-2) tương đương 6 * C(a, 3).
• b(b-1)(b-2) tương đương 6 * C(b, 3).
• a(a-1)b tương đương 2 * C(a, 2) * b.
• b(b-1)a tương đương 2 * C(b, 2) * a. Phương pháp này là tối ưu nhất về mặt hiệu năng cho bài toán này.

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

Bài học kinh nghiệm

• Bài toán có độ dài xâu cố định (3), nên các trường hợp có thể đếm được rất ít và dễ dàng liệt kê (tất cả đều là xâu đối xứng).
• Một xâu độ dài 3 đối xứng khi và chỉ khi ký tự thứ nhất bằng ký tự thứ ba.
• Nếu chỉ quan tâm đến số lượng xâu distinct thỏa mãn giới hạn về số lượng ký tự, công thức là C(n,3) + ...
• Nếu quan tâm đến số cách chọn 3 vị trí từ tập hợp a chữ số '0' và b chữ số '1' (giả sử các chữ số này có thể hoán vị), công thức là a(a-1)(a-2) + ...

Lỗi thường gặp

• Lầm tưởng bài toán yêu cầu đếm số cách chọn 3 vị trí trong chuỗi ban đầu (thường là các số lớn) thay vì đếm số cách tạo xâu mới distinct.
• Quên kiểm tra điều kiện n, m >= 2 hoặc >= 3 trước khi tính tổ hợp.
• Viết sai công thức tổ hợp (Pascal) dẫn đến tràn số nếu không dùng long long.