Lát gạch
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho một hình chữ nhật kích thước \(2 \times N (1\le N\le 10^9)\). Hãy đếm số cách lát các viên gạch nhỏ kích thước \(1\times 2\) và \(2\times 1\) vào hình trên sao cho không có phần nào của các viên gạch nhỏ thừa ra ngoài, cũng không có vùng diện tích nào của hình chữ nhật không được lát.
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ố \(N\).
Output
- Ghi ra \(T\) dòng là số cách lát tương ứng lấy phần dư cho 111539786.
Example
Test 1
Input
3
1
2
3Output
1
2
3
Bình luận
Mình xin chia sẻ lời giải bài này, như sau:
Gọi \(F[n]\) là số cách lát các viên gạch nhỏ \(1\text{ x }2\) và \(2\text{ x }1\) vào hình chữ nhất có kích thước \(2\text{ x }N\) thoả mãn yêu cầu bài toán, khi đó ta sẽ xây dựng công thức \(F[n]\) theo \(2\) cách như sau:
Cách 1: Giả sử ta đã lát được hình chữ nhật có kích thước \(2\text{ x }(N-1)\). Do đó, trường hợp này ta chỉ cần lát thêm \(1\) viên có kích thước \(2\text{ x }1\) là ta thu được hình chữ nhật có kích thước \(2\text{ x }N\). Do vậy ta có: \(F[n-1]\) cách xây dựng thành \(F[n]\) cho trường hợp này.
Cách 2: Giả sử ta đã lát được hình chữ nhật có kích thước \(2\text{ x }(N-2)\). Do đó, trường hợp này ta cũng chỉ có một cách lắp thêm để thu được hình chữ nhật có kích thước \(2\text{ x }N\). Đó là ta xếp \(2\) hình chữ nhật có kích thước \(1\text{ x }2\). (Sở dĩ ta không xếp \(2\) hình chữ nhật có kích thước \(2\text{ x }1\) vì như vậy nó sẽ bị trùng ở cách 1). Do vậy ta có \(F[n-2]\) cách xây dựng \(F[n]\) cho trường hợp này.
Ảnh minh hoạ:
Từ đây ta suy ra được \(F[n]=F[n-1]+F[n-2]\), và ta dễ dàng tính được \(F[1]=1,F[2]=2\).
Tiếp theo, chúng ta sẽ đi tính \(F[n]\). Ta có một nhận xét rằng, vì \(N\sim 10^9\). Nên nếu ta dùng một for thông thì chắc chắn sẽ bị \(TLE\). Nên ở đây, mình sẽ dùng nhân ma trận (một công cụ hữu hiệu để giải những bài toán này) với độ phức tạp là \(O(log(n))\).
Về cách xây dựng, hoàn toàn tương tự cách \(3\) trong lời giải của bài Đo nước nên mình sẽ không trình bày lại, và sẽ ghi kết quả ra đây luôn.
Đó là từ \(F[n] = F[n-1]+F[n-2]\implies \begin{pmatrix} F[n-1] & F[n] \end{pmatrix} . \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} F[n]& F[n+1] \end{pmatrix}\)
Đặt \(p_n = \begin{pmatrix} F[n] & F[n+1] \end{pmatrix}\) và \(M = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}\)
Khi đó ta suy ra được: \(p_n=p_{n-1}.M=...=p_1.M^{n-1}\).
Vậy \(p_n=p_1.M^{n-1}\) , trong đó: \(p_1=\begin{pmatrix} F[1] & F[2] \end{pmatrix}\).
Và công việc còn lại của chúng ta là dùng luỹ thừa nhị phân để tính \(M^{n-1}\) và thực hiện các phép nhân ma trận là xong.
Như vậy là bài toán đã được giải quyết, các bạn có thể xem code của mình tại đây