Xếp Gạch Xây Tường
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Có một bức tường kích thước 2×N. Bạn có các viên gạch kích thước 1×2 và 2×1. Hỏi có bao nhiêu cách xếp gạch để lấp đầy bức tường? In kết quả modulo 10^9 + 7.
Đây là bài toán kinh điển, nhưng với N rất lớn (đến 10^18), bạn cần sử dụng phép nhân ma trận nhanh.
Dữ liệu vào
Một số nguyên N (1 ≤ N ≤ 10^18)
Dữ liệu ra
Một số nguyên — số cách xếp gạch mod 10^9 + 7.
Ví dụ
| Input | Output |
|---|---|
| 4 | 5 |
Giới hạn
- 1 ≤ N ≤ 10^18
Community Discussion