Một bài toán truy hồi
Đề bài
Mô tả
Bạn đang gặp một rắc rối rất lớn! Bạn yêu các hệ thức truy hồi, có lẽ hơi quá mức. Đặc biệt, bạn mê các hệ thức truy hồi tuyến tính dương (PLRR), được định nghĩa như sau. Đầu tiên, bạn chọn bậc của hệ thức. Sau đó bạn chọn các hệ số và phần tử đầu tiên của một dãy số. Hệ thức được gọi là "dương" nếu tất cả các số này đều là số nguyên dương. Phần còn lại của dãy được sinh ra vô hạn theo công thức
Dãy Fibonacci là hệ thức truy hồi nổi tiếng nhất có dạng này, nhưng còn rất nhiều hệ thức khác.
Thật ra, hôm qua, trong một cơn cảm hứng toán học điên rồ, bạn đã viết ra mọi cách có thể để chọn một hệ thức truy hồi tuyến tính dương, cùng với dãy vô hạn tương ứng, lên các tấm thẻ, mỗi tấm một hệ thức. (Bạn có rất nhiều thẻ; bạn mua sỉ.) Mọi chuyện diễn ra hơi mơ hồ. Nhưng sáng nay thức dậy, bạn nhận ra mình không có cách tốt nào để sắp thứ tự hay đánh số các PLRR. Bạn đã thử sắp xếp các dãy theo thứ tự từ điển, nhưng có quá nhiều dãy bắt đầu bằng "1", bạn sẽ không bao giờ đi tới được những dãy phía sau.
May thay, cảm hứng lại đến! Bạn nhận ra rằng có thể sắp các PLRR theo thứ tự từ điển của phần được sinh ra của dãy mà thôi (tức là phần dãy bắt đầu sau giá trị ban đầu: ). Nếu hai PLRR có phần được sinh ra giống hệt nhau, PLRR có dãy hệ số nhỏ hơn theo thứ tự từ điển đứng trước. Ví dụ, , , đứng trước , , , dù phần được sinh ra của hai dãy giống nhau. Cách này cho phép bạn đánh số các tấm thẻ, bắt đầu từ , và mọi tấm thẻ đều được gán một số.
Cho số ghi trên một tấm thẻ, hãy mô tả dãy trên tấm thẻ đó!
Dữ liệu vào
Một dòng duy nhất chứa số nguyên (), chỉ số của PLRR cần tìm.
Dữ liệu ra
In ra bốn dòng mô tả hệ thức truy hồi cần tìm. Dòng thứ nhất chứa bậc . Dòng thứ hai chứa hệ số . Dòng thứ ba chứa giá trị ban đầu . Dòng thứ tư chứa giá trị được sinh ra đầu tiên .
Ràng buộc
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 | 2 1 1 1 1 2 3 5 8 13 21 34 55 89 144 |
Thẻ số là , (phần được sinh ra ). Có ba PLRR có giá trị được sinh ra đầu tiên bằng , theo thứ tự: (), dãy Fibonacci () và (). Vậy thẻ số là dãy Fibonacci. |
| 1235 | 4 1 1 3 1 3 2 1 1 9 15 44 99 255 611 1519 3706 9129 22377 |
, . |
Bình luận