Fill in The Rectangle (public version)
Cho 1 mình chữ nhật n x m. Bạn hãy lấp đầy hình chữ nhật n x m bằng các hình chữ nhật 1 x 1, 2 x 1 và 1 x 2. Hãy tính số cách có thể lấp đầy. Do kết quả rất lớn nên bạn hãy in ra theo modulo 109.
Ví dụ:
- Với n = 2, m = 2. Ta có 7 cách xếp.
[Đầu vào/ Đầu ra]:
- [Giới hạn thời gian]: 1s với C++,6s với Java & C#,8s với Python,Go,Js.
- [Đầu vào]: Integer n
(1 ≤ n ≤ 6). - [Đầu vào]: Long Long m
(1 ≤ m ≤ 1018). - [Đầu ra]: Số cách để lấp đầy hình chữ nhật
n x m.
Post Comment