#1073 · Xâu tam phân

Ta gọi:

f(n) là số xâu có độ dài n không chứa 11 liền kề.

Để tạo công thức truy hồi đầy đủ ta sẽ dùng phương pháp ghép chữ số ở cuối dãy f(n)

Để đơn giản hóa thì ta sẽ biến đổi lại f(n) thành f(n, c) thì trong đó c là chữ số ghép tại vị trí a(n)

Vậy ta sẽ có 3 TH như sau:

TH1: c = 0

f(n, 0) = a(1)a(2)...a(n-2)a(n-1)0
Nếu a(n-1) = 0,1,2 thì đều thỏa mãn vì không chứa 11
=> số xâu thỏa f(n, 0) = f(n-1, 0) + f(n-1, 1) + f(n-1, 2)

TH2: c = 2 (tương tự với c = 0)

=> số xâu thỏa f(n, 2) = f(n-1, 0) + f(n-1, 1) + f(n-1, 2)

TH3: c = 1

f(n, 0) = a(1)a(2)...a(n-2)a(n-1)1
Nếu a(n-1) = 0,2 (loại c=1 vì liền kề 11) thì đều thỏa mãn vì không chứa 11
=> số xâu thỏa f(n, 1) = f(n-1, 0) + f(n-1, 2)

Suy ra công thức đầy đủ là:

f(n, c) = f(n, 0) + f(n, 1) + f(n, 2)

Trong đó:
f(n, 0) = f(n-1, 0) + f(n-1, 1) + f(n-1, 2)
f(n, 1) = f(n-1, 0) + f(n-1, 2)
f(n, 2) = f(n-1, 0) + f(n-1, 1) + f(n-1, 2)

Tiếp theo là tới basecase:

Với n = 1 (xâu 1 ký tự) thì tất cả đều hợp lệ:
=> f(1, c) = 1 (ở đây có 1 xâu thõa mãn)

Vậy ta có thể code đơn giản như sau:

#include <iostream>
#define ll long long
#define MAX 1000000
#define MOD 1000000007
using namespace std;

// Ở đây chưa thêm MOD đâu :v
ll ans(ll n, int c)
{
    if(n == 1) return 1;
    if(c == 0 || c == 2) // TH 1 và 2
        return ans(n-1, 0) + ans(n-1, 1) + ans(n-1, 2);
    else if(c == 1) // TH 3
        return ans(n-1, 0) + ans(n-1, 2);
}

int main() {
    ll n;
    cin >> n;
	// Tương đương: f(n, c) = f(n, 0) + f(n, 1) + f(n, 2)
    cout << ans(n, 0) + ans(n, 1) + ans(n, 2);
    return 0;
}

Ta có công thức truy hồi, code chạy ra => Dùng quy hoạch động.

Đơn giản là ta chỉ lưu trữ để tránh tính toán lại thôi

Code:

#include <iostream>
#define ll long long
#define MAX 1000000
#define MOD 1000000007
using namespace std;

ll dp[MAX+1][3];

ll ans(ll n, int c)
{
    if(n == 1) return 1;
	
	if(dp[n][c] != -1) return dp[n][c]; // Trả về luôn nếu có trong dp
	
    if(c == 0 || c == 2)
        dp[n][c] = ans(n-1, 0) + ans(n-1, 1) + ans(n-1, 2);
    else if(c == 1)
        dp[n][c] = ans(n-1, 0) + ans(n-1, 2);

    return dp[n][c];
}

int main() {
	// Khởi tạo dp
	for(int i=0; i<=MAX; i++)
		for(int j=0; j<=2; j++)
			dp[i][j] = -1;

    ll n;
    cin >> n;
    cout << ans(n, 0) + ans(n, 1) + ans(n, 2);
    return 0;
}

Dùng đệ quy thì dễ bị tràn stack. Thế nên ta sẽ xây từ basecase lên đỉnh

Code:

#include <iostream>
#define ll long long
#define MAX 1000000
#define MOD 1000000007
using namespace std;

ll dp[MAX+1][3];

ll ans(ll n)
{
    dp[1][0] = 1;
    dp[1][1] = 1;
    dp[1][2] = 1;

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

    return dp[n][0] + dp[n][1] + dp[n][2];
}

int main() {
    ll n;
    cin >> n;
    cout << ans(n);
    return 0;
}

Ok nhớ thêm MOD để được AC nhé :))

Cây đệ quy với testcase n = 2

Trong ví dụ này có 8 xâu là: 00, 01, 02, 10, 12, 20, 21, 22

Tóm lại là ta chỉ né 1 ra nếu trước đó là 1 :)))