301203: CF225B. Well-known Numbers
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Well-known Numbers
题意翻译
定义$k$-bonacci数列${Fn}:Fi=0(i<k),Fi=1 (i=k),Fi=\sum_{j=i-k}^{n-1}Fj$ 给出$s\ (s≤10^9)$和$k\ (k≤10^9)$,将$s$拆成若干个$k$-bonacci数之和。题目描述
Numbers $ k $ -bonacci ( $ k $ is integer, $ k>1 $ ) are a generalization of Fibonacci numbers and are determined as follows: - $ F(k,n)=0 $ , for integer $ n $ , $ 1<=n<k $ ; - $ F(k,k)=1 $ ; - $ F(k,n)=F(k,n-1)+F(k,n-2)+...+F(k,n-k) $ , for integer $ n $ , $ n>k $ . Note that we determine the $ k $ -bonacci numbers, $ F(k,n) $ , only for integer values of $ n $ and $ k $ . You've got a number $ s $ , represent it as a sum of several (at least two) distinct $ k $ -bonacci numbers.输入输出格式
输入格式
The first line contains two integers $ s $ and $ k $ $ (1<=s,k<=10^{9}; k>1) $ .
输出格式
In the first line print an integer $ m $ $ (m>=2) $ that shows how many numbers are in the found representation. In the second line print $ m $ distinct integers $ a_{1},a_{2},...,a_{m} $ . Each printed integer should be a $ k $ -bonacci number. The sum of printed integers must equal $ s $ . It is guaranteed that the answer exists. If there are several possible answers, print any of them.
输入输出样例
输入样例 #1
5 2
输出样例 #1
3
0 2 3
输入样例 #2
21 5
输出样例 #2
3
4 1 16