Hiểu bài toán

Bài toán yêu cầu đếm số lượng xâu ký tự độ dài n gồm các ký tự {0, 1, 2} sao cho không có hai ký tự '1' nào liền kề nhau. Với n lên tới 100,000, kết quả cần được in ra sau khi chia dư cho 10^9 + 7.

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

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

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

const long long MOD = 1e9 + 7;

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

    // dp[i][0]: số xâu độ dài i kết thúc bằng 0 hoặc 2
    // dp[i][1]: số xâu độ dài i kết thúc bằng 1
    // Ban đầu với độ dài 1:
    // 0, 2 -> 2 cách (kết thúc bằng 0 hoặc 2)
    // 1 -> 1 cách
    long long dp0 = 2; 
    long long dp1 = 1;

    for (int i = 2; i <= n; ++i) {
        long long new_dp0 = (dp0 + dp1) * 2 % MOD;
        long long new_dp1 = dp0 % MOD;

        dp0 = new_dp0;
        dp1 = new_dp1;
    }

    cout << (dp0 + dp1) % MOD;
    return 0;
}

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

Ta sử dụng biến dp0 để lưu số lượng xâu độ dài i kết thúc bằng ký tự '0' hoặc '2', và dp1 để lưu số lượng xâu kết thúc bằng '1'.

• Nếu thêm '0' hoặc '2' vào cuối xâu cũ (bất kỳ ký tự nào), ta có 2*(dp0 + dp1) cách.
• Nếu thêm '1' vào cuối, xâu cũ phải kết thúc bằng '0' hoặc '2' (để tránh hai '1' liền nhau), nên có dp0 cách. Cập nhật liên tục đến độ dài n để tìm kết quả.

Cách Quy hoạch động dùng mảng

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

const long long MOD = 1e9 + 7;

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

    vector<long long> dp(n + 1);
    dp[0] = 1;
    dp[1] = 3;

    for (int i = 2; i <= n; ++i) {
        dp[i] = (2 * dp[i-1] + 2 * dp[i-2]) % MOD;
    }

    cout << dp[n];
    return 0;
}

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

Đây là cách tiếp cận dựa trên quy hoạch động với công thức tổng quát. Gọi dp[i] là số xâu tam phân độ dài i thỏa mãn điều kiện. Ta xét ký tự đầu tiên của xâu:

• Bắt đầu bằng 0 hoặc 2 (2 cách): phần còn lại là xâu độ dài i-1 bất kỳ -> 2 * dp[i-1]
• Bắt đầu bằng 1 (1 cách): ký tự tiếp theo phải là 0 hoặc 2 (2 cách), phần còn lại là xâu độ dài i-2 bất kỳ -> 2 * dp[i-2] Tổng: dp[i] = 2dp[i-1] + 2dp[i-2].

Cách Ma trận tăng trưởng (Matrix Exponentiation)

// Hàm nhân 2 ma trận
void multiply(long long A[2][2], long long B[2][2]) {
    long long temp[2][2];
    for(int i=0; i<2; i++) {
        for(int j=0; j<2; j++) {
            temp[i][j] = 0;
            for(int k=0; k<2; k++) {
                temp[i][j] = (temp[i][j] + A[i][k] * B[k][j]) % MOD;
            }
        }
    }
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            A[i][j] = temp[i][j];
}

// Hàm tính ma trận M^n
void power(long long F[2][2], int n) {
    if(n == 1) return;
    long long M[2][2] = {{2, 2}, {1, 0}};

    power(F, n/2);
    multiply(F, F);

    if(n % 2 != 0)
        multiply(F, M);
}

long long solve(int n) {
    if (n == 1) return 3;
    long long F[2][2] = {{2, 2}, {1, 0}};
    power(F, n-1);
    // Base case dp[1]=3, dp[0]=1
    // F[0][0] * dp[1] + F[0][1] * dp[0]
    return (F[0][0] * 3 + F[0][1] * 1) % MOD;
}

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

Bài toán có thể quy về dạng tìm số Fibonacci biến đổi. Dựa vào công thức DP: dp[i] = 2dp[i-1] + 2dp[i-2], ta xây dựng ma trận: [ dp[i] ] = [ 2 2 ] [ dp[i-1] ] [ dp[i-1] ] [ 1 0 ] [ dp[i-2] ] Sử dụng phép nhân ma trận lũy thừa nhanh để tính kết quả cho n lớn (trong bài này n chỉ tới 10^5 nên QHĐ là đủ, nhưng đây là cách tối ưu hơn về mặt lý thuyết O(log n)).

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

Bài học kinh nghiệm

• Bài toán có tính chất quy hoạch động do kết quả tại bước i phụ thuộc vào các bước trước đó.
• Có thể giảm số lượng biến lưu trữ xuống O(1) vì chỉ cần giá trị của 2 bước trước đó để tính bước hiện tại.
• Nếu n rất lớn (vd: 10^18), cần phải sử dụng ma trận tăng trưởng để tính trong thời gian O(log n).

Lỗi thường gặp

• Quên chia dư modulo trong mỗi bước tính toán có thể gây tràn số (overflow).
• Xử lý sai trường hợp n = 1 hoặc n = 0 (nếu đề bài cho phép).
• Lầm tưởng rằng có thể sinh tất cả các xâu để kiểm tra (số lượng xâu tăng theo cấp số nhân, không khả thi với n lớn).