Tiles
Xem PDF
Điểm:
1800
Thời gian:
2.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Bạn có vô hạn những viên gạch có hình chữ nhật \(2 \times 1\) và những viện gạch có hình vuông \(2 \times 2\) bị khuất phần tư một góc. Hãy đếm số cách lát những viên gạch này thành một hình chữ nhật \(2 \times N\).
Input
- Gồm nhiều test, dòng đầu ghi số lượng test \(T ( T\le 100 )\).
- \(T\) dòng sau mỗi dòng ghi một số dương \(N(N\leq 10^9)\).
Output
- Ghi ra \(T\) dòng, mỗi dòng chứa số thứ tự của test và số cách lát tương ứng lấy phần dư cho 10007.
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(N \leq 100\)
- Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm
Example
Test 1
Input
2
3
10Output
Case 1: 5
Case 2: 1255
Bình luận
Mình xin chia sẻ lời giải bài này như sau:
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