[#3 dp] easy Lego
Cho 4 mảnh lego có kích thước chiều cao x chiều rộng lần lượt là 1×1, 1×2, 1×3, 1×4, tìm số cách để lấp kín một khối chữ nhật kích thước n x m bằng các mảng lego này. Vì kết quả có thể rất lớn trả về đáp án mod 10 ** 9 + 7 (các mảnh chỉ có thể đặt nằm ngang).
Ví dụ:
- Với
n = 1vàm = 1thì đầu ra củaeasyLego(n,m) = 1. Chỉ có đúng 1 cách lấp đầy hình chữ nhật đó (dùng mảnh 1×1). - Với
n = 1vàm = 2thì đầu ra củaeasyLego(n,m) = 2. Có thể dùng 2 mảnh 1×1 hoặc 1 mảnh 1 x 2 để lấp đầy hình chữ nhật.
Input/Output:
-
[execution time limit] 0.5 seconds
-
[input] integer n
1 ≤ n ≤ 100000.
-
[input] integer m
1 ≤ m ≤ 100000. -
[output] integer
Post Comment