Tích Fibonacci
Đề bài
Mô tả
Dãy Fibonacci được định nghĩa như sau: , , . Một số số hạng đầu tiên của dãy Fibonacci:
Cho một số tự nhiên , hãy đếm số cách biểu diễn thành tích của các số Fibonacci (các số trong biểu diễn phải lớn hơn ). Hai cách biểu diễn chỉ khác nhau về thứ tự các thừa số được coi là một.
Dữ liệu vào
Dòng đầu tiên chứa số bộ dữ liệu (). Mỗi dòng trong dòng tiếp theo chứa một số nguyên ().
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra trên một dòng số cách phân tích thành tích các số Fibonacci.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 2 7 8 40 64 |
1 0 2 2 3 |
Số có một cách biểu diễn duy nhất: . Số không thể biểu diễn thành tích các số Fibonacci. Số có hai cách: và . Số có hai cách: và . Số có ba cách: , và . |
| 5 6 720 1000000 13 4181 |
1 3 3 1 1 |
. . là một số Fibonacci. |
Bình luận