Đếm số cách lát hình chữ nhật bằng các domino (các viên domino lát phủ kín hình chữ nhật, không chờm ra ngoài, không chồng lên nhau).
Chẳng hạn với ta có nhiều cách lát, dưới đây là một trong số đó:
Dữ liệu vào:
- Dòng đầu chứa số nguyên dương là số bộ test;
- dòng tiếp theo, mỗi dòng chứa một số nguyên dương .
Dữ liệu ra:
- Với mỗi , in ra trên một dòng số cách lát tương ứng.
Ví dụ:
Dữ liệu vào:
Dữ liệu ra:
Giải thích:
- Với hoặc , không có cách nào lát được.
- Với ta có cách lát như sau:
Giới hạn: