Editorial for color: Tô màu 2

Hiểu bài toán

Bài toán yêu cầu tính số cách tô màu K ô vuông trên một hàng gồm N ô vuông sao cho hai ô được tô màu không nằm cạnh nhau. N có thể lên tới 10^9 rất lớn, trong khi K tối đa là 5000. Kết quả cần được in ra sau khi chia lấy dư cho 10^9 + 7.

Về bản chất, đây là bài toán chọn K vị trí trong N vị trí sao cho bất kỳ hai vị trí nào cũng cách nhau ít nhất 1 ô trống. Nếu coi các ô được tô là '1' và ô trống là '0', chúng ta cần tìm số xâu nhị phân độ dài N chứa đúng K số 1 và không có hai số 1 nào liền kề.

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

Cách Công thức kết hợp (Combinatorics)

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 MOD = 1000000007;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long N;
    int K;
    cin >> N >> K;

    // Xử lý các trường hợp cơ bản
    if (K == 0) {
        cout << 1 << '\n';
        return 0;
    }
    if (K > (N + 1) / 2) {
        cout << 0 << '\n';
        return 0;
    }

    // Sử dụng biến đổi stars and bars:
    // Số cách chọn K vị trí không cạnh nhau trong N vị trí
    // tương đương với việc chọn K vị trí trong N - K + 1 vị trí.
    long long M = N - K + 1;

    // Tính C(M, K) = M! / (K! * (M-K)!)
    // Do N rất lớn, ta không thể tính giai thừa của M.
    // Tuy nhiên, K nhỏ (<= 5000), nên ta có thể tính:
    // Tu so = M * (M-1) * ... * (M-K+1)
    // Mau so = K!

    int64 tu = 1;
    for (int i = 0; i < K; i++) {
        tu = (tu * ((M - i) % MOD)) % MOD;
    }

    int64 mau = 1;
    for (int i = 1; i <= K; i++) {
        mau = (mau * i) % MOD;
    }

    // Tính nghịch đảo modulo của Mau
    int64 inv_mau = modpow(mau, MOD - 2);

    cout << (tu * inv_mau) % MOD << '\n';
    return 0;
}

• Time Complexity: O(K log MOD)
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp và hiệu quả nhất.

1. Biến đổi bài toán: Giả sử ta chọn được K vị trí thỏa mãn. Gọi các vị trí được chọn là x1, x2, ..., xK. Ta có điều kiện xi+1 >= xi + 2 (vì không được cạnh nhau).
2. Stars and Bars: Đặt yi = xi - (i-1). Khi đó điều kiện trở thành yi+1 >= yi + 1, nghĩa là các y_i là các số nguyên dương phân biệt. Nhưng để dùng công thức tổ hợp chuẩn, ta thường biến đổi về bài toán chọn K số không phân biệt trong một tập hợp mới.
   • Khoảng cách từ ô đầu tiên đến ô cuối cùng (bắt đầu bằng 1 và kết thúc bằng N) chia làm K+1 đoạn: trước ô đầu tiên, giữa các ô được chọn, và sau ô cuối cùng.
   • Các khoảng trống giữa các ô được chọn (K-1 khoảng) phải có độ dài >= 1.
   • Gọi z0, z1, ..., zK là số lượng trống ở các đoạn tương ứng. Ta có z0 + z1 + ... + zK = N - K.
   • Với z1, ..., z(K-1) >= 1. Đặt z'i = zi - 1 cho i = 1..K-1. Ta có z0 + z'1 + ... + z'(K-1) + zK = N - 2K + 2.
   • Số cách phân phối là bài toán Stars and Bars: C((N - 2K + 2) + (K+1) - 1, (K+1) - 1) = C(N - K + 1, K).
3. Tính toán: Kết quả là tổ hợp chập K của (N - K + 1). Vì N rất lớn nhưng K nhỏ, ta tính tử số là tích của K số hạng: (N-K+1) * (N-K) * ... * (N-2K+2). Mẫu số là K!. Sau đó nhân với nghịch đảo modulo của K!.

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

// Pseudo-code for DP approach
// Chỉ khả thi nếu N nhỏ, nhưng tổng quát để hiểu.
// dp[i][j] = số cách tô j ô trong i ô cuối cùng.
// Công thức: dp[i][j] = dp[i-1][j] + dp[i-2][j-1]
// (ô i không được tô + ô i được tô (ô i-1 không được tô))

// Để tối ưu cho N lớn, ta dùng ma trận lũy thừa.
// Biến đổi bài toán thành tính số cách đi trên đồ thị.
// Tuy nhiên, giải pháp này phức tạp và dễ sai.
// Code dưới đây là minh họa logic DP cơ bản (chỉ chạy được nếu N nhỏ).

int main() {
    // Giả lập N nhỏ
    long long N_small = 5; 
    int K = 2;

    // dp[i][j]
    vector<vector<long long>> dp(N_small + 1, vector<long long>(K + 1, 0));

    // Base case: 0 ô thì có 1 cách (không tô gì)
    for (int i = 0; i <= N_small; i++) dp[i][0] = 1;

    for (int i = 1; i <= N_small; i++) {
        for (int j = 1; j <= K; j++) {
            // Trường hợp ô i không tô
            dp[i][j] = dp[i-1][j];
            // Trường hợp ô i tô (phải bỏ qua ô i-1)
            if (i >= 2) {
                dp[i][j] = (dp[i][j] + dp[i-2][j-1]) % MOD;
            } else if (i == 1 && j == 1) {
                dp[i][j] = 1;
            }
        }
    }
    cout << dp[N_small][K] << endl;
    return 0;
}

• Time Complexity: O(N*K) hoặc O(K^3 log N) nếu dùng ma trận
• Space Complexity: O(N*K) hoặc O(K^2)

Sử dụng quy hoạch động để giải quyết bài toán.

1. Định nghĩa: dp[i][j] là số cách chọn j ô trong dãy i ô thỏa mãn điều kiện.
2. Công thức:
   • Nếu ô thứ i không được chọn: có dp[i-1][j] cách.
   • Nếu ô thứ i được chọn: ô i-1 không được chọn, có dp[i-2][j-1] cách (hoặc dp[i-1][j-1] với điều kiện i-1 không chọn).
   • dp[i][j] = dp[i-1][j] + dp[i-2][j-1].
3. Vấn đề: N lên tới 10^9, nên không thể khai báo mảng kích thước N. Cần sử dụng kỹ thuật nâng cao như nhân ma trận (Matrix Exponentiation) để tính dp[N][K] trong thời gian O(K^3 log N).
4. Tại sao không chọn: Mặc dù về mặt lí thuyết có thể dùng DP + Matrix Exponentiation, nhưng với K <= 5000, ma trận kích thước K x K là quá lớn (25 triệu phần tử) và phép nhân ma trận sẽ rất chậm (O(K^3)). Do đó, cách tiếp cận này không khả thi trong thực tế cho giới hạn đề bài.

Cách Sử dụng BIT/Fenwick Tree (Không khả thi với N lớn)

// Ý tưưởng này chỉ để tham khảo, không khả thi với N=10^9
// Logic: Duyệt qua các ô, dùng BIT để đếm số cách kết thúc tại ô đó.
// Tuy nhiên, vì N quá lớn, ta cần tối ưu hóa.
// Thay vào đó, ta có thể nhận thấy bài toán là bài toán tìm tổng quỹ đạo (Lattice Path)
// Tương đương với bài toán đi trong lưới.

// Tuy nhiên, giải pháp tốt nhất vẫn là công thức combinatorics.
// Code dưới đây là cách tiếp cận nếu N nhỏ (vùng chứa DP).

const int MAXN = 1000005;
long long dp[MAXN];

int main() {
    long long N; int K;
    cin >> N >> K;
    // Code này chỉ chạy được nếu N nhỏ
    if (N > 1000000) {
        cout << "N too large for this approach" << endl;
        return 0;
    }
    // Logic DP khác:
    // dp[i] là số cách chọn số lượng ô bất kỳ thỏa mãn.
    // Ta cần tracking số lượng ô đã chọn.
    // Đây là cách tiếp cận sai lệch so với bài toán gốc nếu chỉ dùng 1 chiều.
    return 0;
}

• Time Complexity: O(N) hoặc O(N*K)
• Space Complexity: O(N)

Các solution được cung cấp không dùng BIT/Fenwick Tree. Tuy nhiên, BIT thường được dùng trong các bài toán quy hoạch động trên dãy số. Trong bài toán này, nếu N nhỏ, ta có thể dùng quy hoạch động O(N*K). Nếu N lớn, BIT không giúp ích trực tiếp trừ khi kết hợp với ma trận. Giải pháp tối ưu nhất vẫn là Công thức kết hợp đã nêu ở Approach 1. Approach này được đưa vào để minh họa các dạng bài toán tương tự (ví dụ: N <= 10^5, K <= 10^5) nhưng không phù hợp với ràng buộc hiện tại.

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

Bài học kinh nghiệm

• Biến đổi bài toán 'không chọn 2 ô liền kề' thành bài toán chọn K vị trí trong N - K + 1 vị trí bằng phương pháp Stars and Bars (hoặc biến đổi biến số). Số cách bằng C(N - K + 1, K).
• Vì N rất lớn (10^9) nhưng K nhỏ (5000), ta không thể tính giai thừa của N. Thay vào đó, tính tử số là tích K số hạng liên tiếp, và tính mẫu số là K! rồi dùng Fermat's Little Theorem để chia.
• Kiểm tra các trường hợp đặc biệt ngay từ đầu: K=0 trả về 1, K > (N+1)/2 trả về 0.

Lỗi thường gặp

• Lỗi số học khi tính toán: không lấy modulo đều đặn dẫn đến tràn số (overflow) ngay cả với int64.
• Sai công thức combinatorics: nhầm lẫn giữa C(N, K) và C(N-K+1, K).
• Quên xử lý trường hợp K=0 hoặc K=1.