Xếp Gạch Xây Tường

Buổi 64 — Contest Chặng 7 Dynamic Programming
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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
Draft saved