| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P185SUMD - ROUND 5D - Lát gạch |
Thử thách ngày hôm nay đối với Lù nhà ta khá đơn giản như sau:
Có một khoảng sân hình chữ nhật có kích thước 2 x N ô vuông, gồm 2 hàng và N cột. Đánh số hàng từ 1 đến 2 theo thứ tự từ trên xuống dưới, đánh số cột từ 1 đến n theo thứ tự từ trái qua phải. Lù phải lát sân bằng gạch màu trắng và điểm xuyết một số ô gạch màu đen, mỗi ô vuông được lát bởi một viên gạch, sao cho không có hai viên gạch màu đen nào chung cạnh với nhau. Hỏi có tất cả bao nhiêu cách khác nhau để lát khoảng sân trên (hai cách lát sân được gọi là khác nhau nếu tồn tại tối thiểu một ô ở dòng i cột j được lát gạch màu trắng ở cách này và lát gạch màu đen ở cách kia).
Ví dụ với n = 2, ta có 7 cách lát sân sau đây:
Input
Là một số nguyên n (1 ≤ n ≤ 5.103).
Output
Là số cách lát gạch theo yêu cầu. Số lượng cách có thể cách có thể rất lớn nên lấy dư cho 109 + 7.
Example
Input: 3 Output: 17
| Được gửi lên bởi: | adm |
| Ngày: | 2018-08-03 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
