[QHĐ]Lát gạch 3*n – LATGACH3 – M3TILE

Đề bài: http://vn.spoj.pl/problems/M3TILE/

Đếm số cách lát hình chữ nhật 3xn bằng các domino 2×1?

Dữ liệu vào gồm nhiều testcase kết thúc là số -1.
Mỗi testcase là một số nguyên n, 0 ≤ n ≤ 30.
Với mỗi test case, in ra số nguyên là đáp số trên một dòng.
SAMPLE INPUT
2
8
12
-1
SAMPLE OUTPUT
3
153
2131
Time: 1s
Chú ý: n=0 kết quả trả về là 1.

Bài này thì với n lẻ thì số ô 1×1 là lẻ trong khi các con domio đều có 2 ô, tổng của chúng luôn luôn chẵn, nên kết quả bài toán trả về là 0 có cách xếp nào phù hợp. Do đó ta chỉ xét với n chẵn.
Đầu tiên xét hình chữ nhật 3×2, dễ dàng nhận thấy có 3 cách xếp

Xét tiếp hình chữ nhật 3×4, 3 x 3 = 9 cách + 2 cách => 11 cách

Xét tiếp hình chữ nhật 3×6, ta có các trường hợp sau:

Nếu gọi f(k) là số cách lát hình chữ nhật 3xk thì ta có:
f(6) = f(2) * f(6-2) + 2*[ f(6-4) + f(6-6) ] = 3*11 + 2*(3+1) = 41 cách.
Tổng quát ta có:
f(k) = 3*f(k-2) + 2*[ f(k-4) + f(k-6) + .. + f(0) ]
=> f(k) + f(k-4) = 3*f(k-2) + 3*f(k-4) + 2*[ f(k-6) + f(k-8) + .. + f(0) ]
=> f(k) + f(k-4) = 3*f(k-2) + f(k-2) = 4*f(k-2)
=> f(k) = 4*f(k-2) – f(k-4)
Như vậy là ta đã tìm được công thức truy hồi ngắn gọn như sau:
f(k) = 4*f(k-2) – f(k-4) với f(0) = 1, f(2) = 3
f(n) chính là lời giải cho bài toán. Cài đặt như sau (time: 0.01s