B. Сайн мэдэх тоонууд

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бүхэл $k$$(k>1)$ тооны хувьд $k-bonacci$ гэдэг нь бидний сайн мэдэх Фибоначчи тооны ерөнхий хэлбэр ба дараах чанар бүхий тоог хэлнэ:

  • $1≤n
  • $F(k,k)=1$
  • $n>k$ байх $n$ тооны хувьд $F(k,n)=F(k,n-1)+F(k,n-2)+...+F(k,n-k)$

$k-bonacci$-ийн хувьд зөвхөн $n$, $k$ тоонууд бүхэл үед тодорхойлогдохыг санаарай. Танд $s$ болон $k$ тоонууд өгсөн бол $s$ тоог хэд хэдэн(ядаж хоёр) ялгаатай $k-bonacci$ тоонуудын нийлбэрт тавьна уу.

Оролт

$s$ болон $k$ $(1 ≤ s,k ≤ 10^9;\ k>1)$ тоонууд өгөгдөнө.

Гаралт

Эхний мөрөнд нийлбэрийг элементүүдийн тоо болох $m$ ($m ≥ 2$) тоо байна. Дараагийн мөрөнд нийлбэр нь $s$-тэй тэнцүү байх $m$ ширхэг $k-bonacci$ тоог хэвлэнэ. Оролт бүр боломжит хариутай байх ба хэрэв хэд хэдэн хариу байвал алийг нь ч хэвлэсэн болно.

Орчуулсан: Naranbayar

Жишээ тэстүүд

Оролт
5 2
Гаралт
3
0 2 3
Оролт
21 5
Гаралт
3
4 1 16
Сэтгэгдлүүдийг ачааллаж байна...