Hiểu bài toán

Bài toán yêu cầu đếm số cách đặt 2N viên bi lên một bảng 2 hàng N cột sao cho:

1. Viên bi đầu tiên có thể đặt ở bất kỳ ô trống nào.
2. Các viên bi tiếp theo phải đặt vào ô trống và kề (chung đỉnh) với ít nhất một ô đã có bi. Điều này tương đương với việc tạo ra một dãy các ô được đánh dấu sao cho mỗi ô mới được thêm vào đều kề với một ô đã có trong dãy. Cuối cùng, tất cả 2N ô phải được lấp đầy. Đề bài yêu cầu in kết quả modulo 10^9+7 cho nhiều test case với N lên tới 1000.

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

Cách Quy hoạch động

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<long long> dp(N + 1);
        dp[1] = 2;
        for (int i = 2; i <= N; i++) {
            // Công thức cộng dồn
            dp[i] = (dp[i-1] * (12 + 8*(i-2))) % MOD;
        }
        cout << dp[N] << "\n";
    }
    return 0;
}

• Time Complexity: O(N) mỗi test case (hoặc O(max_N) precompute)
• Space Complexity: O(N)

Cách tiếp cận này dựa trên quy hoạch động hoặc nhận thấy quy luật sinh.

• Với N=1, có 2 cách.
• Khi mở rộng từ bảng cỡ N-1 lên N, ta có thể chèn cột mới vào các vị trí khác nhau hoặc thêm vào các hàng. Công thức tìm thấy: $f(N) = f(N-1) \times (12 + 8(N-2))$.
• Với N=2: $f(2) = 2 \times 12 = 24$.
• Với N=3: $f(3) = 24 \times (12 + 8) = 24 \times 20 = 480$. Cách này tính toán tuần tự từ 1 đến N, độ phức tạp chấp nhận được với N=1000.

Cách Công thức toán học

#include <iostream>
#include <vector>

using namespace std;
using int64 = long long;
const int64 MOD = 1000000007LL;

int64 modpow(int64 a, int64 e) {
    int64 r = 1;
    while (e > 0) {
        if (e & 1) r = (r * a) % MOD;
        a = (a * a) % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        // Tính giai thừa 2N và N
        int64 fact2N = 1, factN = 1;
        for (int i = 1; i <= 2*N; i++) fact2N = (fact2N * i) % MOD;
        for (int i = 1; i <= N; i++) factN = (factN * i) % MOD;

        // Công thức: f(N) = 2^{N-1} * (2N)! / N!
        int64 invN = modpow(factN, MOD - 2);
        int64 res = fact2N * invN % MOD;
        if (N > 1) {
            res = res * modpow(2, N - 1) % MOD;
        }
        cout << res << "\n";
    }
    return 0;
}

• Time Complexity: O(N) mỗi test case
• Space Complexity: O(1)

Đây là cách tiếp cận dựa trên công thức số học chính xác. Số cách đặt được chứng minh là: $$ f(N) = \frac{(2N)!}{N!} \times 2^{N-1} $$

• $(2N)! / N!$: Đại diện cho số cách sắp xếp 2N viên bi (mỗi ô một viên) nhưng coi các viên bi trong cùng một cột là không phân biệt (hoặc có thứ tự cố định).
• $2^{N-1}$: Đại diện cho các cấu trúc 'kênh' hoặc cách chọn thứ tự các cột. Cách này yêu cầu tính giai thừa và lũy thừa mô-đun, độ phức tạp phụ thuộc vào N.

Cách Optimized Precomputation

#include <iostream>
#include <vector>

using namespace std;
using int64 = long long;
const int64 MOD = 1000000007LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    vector<int> qs(T);
    int maxN = 0;
    for (int i = 0; i < T; ++i) {
        cin >> qs[i];
        if (qs[i] > maxN) maxN = qs[i];
    }

    // Precompute answers up to maxN
    vector<int64> ans(maxN + 1);
    ans[1] = 2;
    for (int i = 2; i <= maxN; ++i) {
        ans[i] = (ans[i-1] * (12 + 8*(i-2))) % MOD;
    }

    for (int i = 0; i < T; ++i) {
        cout << ans[qs[i]] << "\n";
    }
    return 0;
}

• Time Complexity: O(T + maxN)
• Space Complexity: O(maxN)

Đây là phiên bản tối ưu cho nhiều test case. Thay vì tính toán lại từ đầu cho mỗi test case, ta đọc hết các giá trị N, tìm giá trị lớn nhất (maxN), rồi tính toán mảng kết quả từ 1 đến maxN một lần duy nhất. Sau đó chỉ cần tra cứu mảng này để trả lời các test case. Độ phức tạp thời gian là tuyến tính tổng quát, rất nhanh cho N=1000 và T lớn.

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

Bài học kinh nghiệm

• Bài toán có thể giảm về bài toán đếm số cách điền các cột (từ trên xuống hoặc trái sang phải) với các ràng buộc chồng lên nhau.
• Công thức cơ sở cho N=1 là 2 cách (đặt bi ở hàng trên hoặc hàng dưới). Công thức tổng quát tìm thấy là $f(N) = 2^{N-1} \times \frac{(2N)!}{N!}$.
• Quy luật truy hồi: $f(N) = f(N-1) \times (12 + 8(N-2))$ cho phép tính nhanh.

Lỗi thường gặp

• Tràn số nguyên khi tính giai thừa hoặc lũy thừa. Cần sử dụng long long và chia lấy dư liên tục.
• Sai công thức lũy thừa modulus: cần dùng thuật toán bình phương nhị phân (binary exponentiation) thay vì lặp đơn giản.
• Xử lý sai trường hợp N=1 trong các công thức có chứa số mũ âm hoặc chia cho 0.