Editorial for bitstr: Đếm số lượng số nhị phân

Hiểu bài toán

Bài toán yêu cầu đếm số lượng xâu nhị phân độ dài N chứa ít nhất một đoạn gồm K số 1 liên tiếp. Kết quả cần in ra là số dư khi chia cho 1,000,007. N có thể lên tới 100,000 và K lên tới 100. Thay vì đếm trực tiếp các xâu thỏa mãn, ta có thể đếm các xâu KHÔNG thỏa mãn rồi lấy tổng số xâu (2^N) trừ đi. Một xâu không chứa K số 1 liên tiếp có nghĩa là trong xâu, số lượng số 1 liên tiếp bất kỳ đều không vượt quá K-1.

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

Cách Quy hoạch động cơ bản

int dp[100005][105] = {0};
// dp[i][j]: số xâu độ dài i kết thúc bằng j số 1 liên tiếp (j < K)
// Công thức:
// dp[i][0] += dp[i-1][t] (với mọi t từ 0 đến K-1) // Thêm '0'
// dp[i][j] += dp[i-1][j-1] (với j từ 1 đến K-1) // Thêm '1'

• Time Complexity: O(N*K)
• Space Complexity: O(N*K)

Sử dụng quy hoạch động với trạng thái dp[i][j] là số xâu nhị phân độ dài i mà đoạn 1 liên tiếp dài nhất ở cuối xâu có độ dài j. Điều kiện là j < K.

• Nếu thêm '0' vào cuối xâu độ dài i-1, đoạn 1 liên tiếp ở cuối bị ngắt, độ dài quay về 0.
• Nếu thêm '1' vào cuối xâu độ dài i-1 có j-1 số 1 ở cuối, độ dài trở thành j. Cách này tốn bộ nhớ O(NK) và thời gian O(NK). Với N=100,000 và K=100, số phép tính là 10^7, có thể chấp nhận được nhưng cần tối ưu bộ nhớ.

Cách Quy hoạch động tối ưu (O(N*K))

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

static const int MOD = 1000007;

int main() {
    int N, K;
    cin >> N >> K;

    vector<int> dp(K, 0), newdp(K, 0);
    dp[0] = 1;

    for (int i = 0; i < N; i++) {
        fill(newdp.begin(), newdp.end(), 0);
        for (int j = 0; j < K; j++) {
            if (dp[j] == 0) continue;
            // Thêm '0': reset về 0
            newdp[0] = (newdp[0] + dp[j]) % MOD;
            // Thêm '1': tăng độ dài lên 1 (nếu chưa đạt K)
            if (j + 1 < K) {
                newdp[j + 1] = (newdp[j + 1] + dp[j]) % MOD;
            }
        }
        dp.swap(newdp);
    }

    int bad = 0;
    for (int j = 0; j < K; j++) {
        bad = (bad + dp[j]) % MOD;
    }

    // Tổng số xâu là 2^N
    int total = 1;
    for (int i = 0; i < N; i++) total = (total * 2) % MOD;

    int ans = (total - bad + MOD) % MOD;
    cout << ans;
    return 0;
}

• Time Complexity: O(N*K)
• Space Complexity: O(K)

Đây là phiên bản tối ưu của Approach 1. Thay vì dùng mảng 2 chiều dp[N][K], ta dùng hai mảng 1 chiều dp và newdp kích thước K để lưu trạng thái của bước hiện tại và bước tiếp theo. Việc này giảm bộ nhớ từ O(N*K) xuống O(K). Logic tính toán tương tự: mỗi bước ta cập nhật các cách tạo xâu mới dựa trên xâu cũ, đảm bảo không vượt quá K-1 số 1 liên tiếp.

Cách Quy hoạch động tối ưu (O(N))

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

const int MOD = 1000007;
int n, k;
int pre[100005]; // pre[i] = sum(dp[0]...dp[i])
int dp[100005];  // dp[i]: số xâu độ dài i kết thúc bằng 1 đoạn 1 liên tiếp (độ dài bất kỳ < K)

int main() {
    cin >> n >> k;

    if (k > n) {
        cout << 0;
        return 0;
    }

    dp[0] = 1;
    pre[0] = 1;

    for (int i = 1; i <= n; i++) {
        if (i < k) {
            dp[i] = pre[i-1];
        } else {
            int pos = i - k - 1;
            dp[i] = (pre[i-1] - (pos >= 0 ? pre[pos] : 0)) % MOD;
            if (dp[i] < 0) dp[i] += MOD;
        }
        pre[i] = (pre[i-1] + dp[i]) % MOD;
    }

    int ans = (1LL * (1 << (n%25)) * ... ) % MOD; // Tính 2^n
    // Hoặc đơn giản hơn: tổng tất cả xâu - xâu tốt
    // Xấu là sum(dp[i]) từ i=0 đến n
    // Tốt = 2^n - Xấu
    int bad = pre[n];
    // Tính 2^n % MOD
    int total = 1;
    for(int i=0; i<n; i++) total = (1LL * total * 2) % MOD;

    cout << (total - bad + MOD) % MOD;
    return 0;
}

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

Phương pháp này tối ưu hơn nữa về mặt thời gian. Thay vì lặp qua K trạng thái ở mỗi bước i, ta tính toán trực tiếp số xâu tốt (bad) cho độ dài i bằng tổng số xâu tốt của các bước trước đó. Công thức:

• Nếu i < K: Xâu độ dài i tốt toàn bộ (vì chưa đủ K phần tử để违反 điều kiện). dp[i] = tổng số xâu độ dài i-1 tốt = pre[i-1].
• Nếu i >= K: Xâu độ dài i tốt = (Tổng xâu độ dài i-1 tốt) - (Xâu độ dài i-K-1 tốt mà nếu thêm K số 1 sẽ thành xâu xấu). dp[i] = pre[i-1] - pre[i-k-1]. Cách này giảm độ phức tạp thời gian xuống O(N) do mỗi bước chỉ làm 1 phép tính.

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

Bài học kinh nghiệm

• Bài toán có thể chuyển đổi về đếm số xâu KHÔNG chứa K số 1 liên tiếp (xâu 'tốt') bằng phương pháp loại trừ.
• Một xâu 'tốt' độ dài N được tạo ra bằng cách nối các khối 0 và các khối 1 có độ dài từ 1 đến K-1.
• Quy hoạch động dựa trên độ dài đoạn 1 liên tiếp cuối cùng giúp kiểm soát điều kiện ràng buộc.

Lỗi thường gặp

• Làm tròn hoặc sai số khi thực hiện phép chia lấy dư với số âm.
• Quên kiểm tra điều kiện K > N (lúc này đáp án luôn là 0).
• Tính sai số mũ 2^N với N lớn (cần thực hiện lũy thừa nhanh hoặc lặp).