Mình xin chia sẻ lời giải bài này như sau:

• Trước hết mình có một nhận xét đặc biệt sau: Đối với \(n\) chẳn, và \(n\) lẻ. Thì ngoài các cách lát chỉ toàn với viên gạch có kích thước, \(1 * 2\), ta có thể có những cách lát xen kẻ giữa \(1 * 2\) và hình vuông "khuất một góc" để tạo thành hình chữ nhật có kích thước \(2 * n\). Các bạn có thể xem hình bên dưới.

Cụ thể như sau:

• Đối với \(n\) lẻ: Ta có \(2\) cách để xây dựng hình chữ nhật có kích thước \(2 * n\) bằng cách xếp cách viên gạch hình vuông "khuất một góc" hai đầu, và sau đó lắp đầy hình chữ nhật \(2 * n\) bằng những viên gạch \(1 * 2\)

• Đối với \(n\) chẳn: Hoàn toàn tương tự \(n\) lẻ, ta cũng có \(2\) cách để xây dựng với các viên gạch \(1 * 2\) và viên gạch hình vuông "khuất một góc" xen kẻ.

Khi đó ta xây dựng công thức truy hồi cho bài toán này như sau:

Gọi \(f(n)\) là số cách lát thoả mãn yêu cầu bài toán, khi đó: \(f(n)=f(n-1)+f(n-2)+2 * f(n-3)+...+2*f(0)(*)\)

Để dễ hiểu hơn, các bạn có thể xem hình dưới đây:

Do đó bây giờ ta chỉ quan tâm cách tính \(f(n)\) sao cho thoả mãn độ phức tạp là được.

Đến đây, ta tiếp tục xử lý như sau:
Đặt \(g(n)=f(n)+f(n-1)+...+f(0)\).
Khi đó ta có: \(\left\{\begin{matrix}f(n)=g(n-1)+g(n-3)(1)\\ f(n)=g(n)-g(n-1)(2)\end{matrix}\right.\iff \left\{\begin{matrix}g(n)-g(n-1)=g(n-1)+g(n-3)(3)\\ f(n)=g(n)-g(n-1)(4)\end{matrix}\right.\)

Từ \((3)\implies g(n)=2g(n-1)+g(n-3)\), với \(g(0)=1,g(1)=1,g(2)=4\)

Đến đây, để giải quyết subtask với \(n\sim 10^9\). Ta sử dụng bài toán nhân ma trận quen thuộc.

Cụ thể như sau: Đặt \(p_n=\begin{pmatrix}g(n-1) & g(n-2) & g(n-3)\end{pmatrix}\) và \(M=\begin{pmatrix}2&1&0 \\ 0&0&1\\ 1&0&0\end{pmatrix}\). Ta có: \(p_{n+1}=p_n * M=...=p_3*M^{n-2}\).

Trong đó \(p(3)=\begin{pmatrix}4&2&1\end{pmatrix}\)

Đến đây sử dụng luỹ thừa nhị phân với phép toán ma trận ta tính được \(p_{n+1}\). Và từ đây ta suy ra được \(f(n)=g(n)-g(n-1)\).
Như vậy là bài toán đã được giải quyết xong. Nếu có gì thắc mắc, các bạn cứ comment nhé.

Ps:

• Để biết nhân ma trận là gì, các bạn có thể tham khảo bài Đo nước

• Các bạn có thể tham khảo code của mình tại đây: Link