trang chủ / đề bài / icpcwf23_e

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 k của hệ thức. Sau đó bạn chọn các hệ số c1,c2,…,ck và k phần tử đầu tiên a1,a2,…,ak 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

ai+k=c1·ai+c2·ai+1+…+ck·ai+k−1với i≥1.

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 k giá trị ban đầu: ak+1,ak+2,…). Nếu hai PLRR có phần được sinh ra giống hệt nhau, PLRR có dãy hệ số (c1,…,ck) nhỏ hơn theo thứ tự từ điển đứng trước. Ví dụ, k=1, c1=2, a1=2 đứng trước k=2, (c1,c2)=(2,1), (a1,a2)=(1,2), 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ừ 1, 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 n (1≤n≤109), 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 k. Dòng thứ hai chứa k hệ số c1,…,ck. Dòng thứ ba chứa k giá trị ban đầu a1,…,ak. Dòng thứ tư chứa 10 giá trị được sinh ra đầu tiên ak+1,…,ak+10.

Ràng buộc

  • 1≤n≤109.

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ố 1 là k=1, c1=a1=1 (phần được sinh ra 1,1,1,…). Có ba PLRR có giá trị được sinh ra đầu tiên bằng 2, theo thứ tự: c1=1,a1=2 (2,2,2,…), dãy Fibonacci (2,3,5,…) và c1=2,a1=1 (2,4,8,…). Vậy thẻ số 3 là dãy Fibonacci.
1235 4
1 1 3 1
3 2 1 1
9 15 44 99 255 611 1519 3706 9129 22377
a5=1·3+1·2+3·1+1·1=9, a6=1·2+1·1+3·1+1·9=15.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0