BZPRO
#5547. [PA2019]Iloczyny Fibonacciego
内存限制：768 MiB
时间限制：200 Sec
提交
提交记录
讨论
题目描述
定义斐波那契数列为F[1]=1,F[2]=2,F[i]=F[i-1]+F[i-2](i>=3)。
对于任意一个正整数x，我们总能将x写成唯一的斐波那契表示(b[1],b[2],...,b[n])，满足：
1. b[1]*F[1]+b[2]*F[2]+...+b[n]*F[n]=x。
2. 对于任意的i(1<=i<n)都有b[i]=0或b[i]=1；对于b[n]有b[n]=1。
3. 对于任意的i(1<=i<n)都有b[i]*b[i+1]=0。
比如2=(0,1),4=(1,0,1),5=(0,0,0,1),20=(0,1,0,1,0,1)=F[2]+F[4]+F[6]=2+5+13。
给定两个斐波那契表示的正整数A和B，请输出A*B的斐波那契表示。
输入格式
第一行包含一个正整数T(1<=T<=1000)，表示测试数据的组数。
每组测试数据包含两行，分别描述A和B的斐波那契表示。每行首先是一个正整数n，然后n个非负整数b[1],b[2],...,b[n]。
输入数据保证所有的n加起来不超过1000000。
输出格式
对于每组数据输出一行，按照输入格式输出A*B的斐波那契表示。
样例
样例输入
2
3 1 0 1
4 0 0 0 1
2 0 1
1 1
样例输出
6 0 1 0 1 0 1
2 0 1
数据范围与提示
BZPRO