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
10
Output
Case 1: 5
Case 2: 1255

Bình luận


  • 6
    jumptozero 11:47 a.m. 26 Tháng 5, 2021

    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}\)\(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