黑暗爆炸OJ
DARKBZOJ
Statistics
下载数据
Description
Fibbonacci 数列是这样定义的: Fib0 = 1, Fib1 = 1, Fibi = Fibi-2 + Fibi-1 (for i >= 2). 数列的前几项是: (1, 1, 2, 3, 5, 8,...).
任意一个整数都可以表示为若干个不同的Fib数的和,但为了保证表示的唯一性,我们用 (b1, b2,..., bn) 表示数b1 . Fib1 + b2 . Fib2 + ... + bn . Fibn. (我们没有用Fib0.). 并且有如下规定:
· 如果 n > 1, 则 bn = 1, 即表示的数没有前导0.
· 如果 bi = 1, 那么 bi+1 = 0 (for i = 1,..., n - 1), 即表示中不· 存在连续的两个0.
给出两个数的Fib表示,求他们的和的Fib表示.
Input
第一行一个整数N表示第一个数的Fib表示长度,接下来N个数字0或者1.
第二行和第一行格式相同描述第二个数, 1 <= n <= 1 000 000.
Output
一个整数n代表输入的两个数的和的Fib表示的长度,接下来n个数代表表示方案, 1 <= n <= 1 000 000.Sample Input
Sample Output
Hint
Source
