#P17849. [Ontak2019]FIB

[Ontak2019]FIB

— 斐波那契进制除法

定义斐波那契数列:

$$F_0=1,\qquad F_1=2,\qquad F_i=F_{i-1}+F_{i-2}\quad(i\ge2).$$

每个非负整数 xx 都有唯一的标准斐波那契进制表示 (b0,b1,…,bn−1)(b_0,b_1,\ldots,b_{n-1}),满足:

  • x=∑i=0n−1biFix=\sum_{i=0}^{n-1}b_iF_i;
  • 每位为0或1,非零数的最高位 bn−1=1b_{n-1}=1;
  • 不存在两个相邻的1。

整数0的表示长度为0。注意输入和输出均按低位在前、高位在后的顺序给出各位。

给定一个正整数 xx 的标准斐波那契进制表示,以及 1≤k≤31\le k\le3,求 ⌊x/k⌋\lfloor x/k\rfloor 的标准斐波那契进制表示。

输入格式

第一行一个整数 zz,表示测试用例数。

每个测试用例占两行:第一行先给出位数 nn,然后是 nn 个整数 b0,b1,…,bn−1b_0,b_1,\ldots,b_{n-1};第二行给出除数 kk。

输出格式

每个测试用例输出一行:先输出答案的位数 n′n',再输出 n′n' 个二进制位,仍按低位在前的顺序。

若商为0,只输出一个整数 0,不要输出 1 0。

数据范围

1≤z≤1001\le z\le100,1≤n≤20000001\le n\le2000000,1≤k≤31\le k\le3。所有用例的 nn 之和不超过20000000。保证输入表示合法且表示正整数。英文版漏写了 zz 的上限,这里按同一 PDF 中的波兰文版本补全。

子任务 附加限制 分值
1 n≤50n\le50 10
2 n≤10000n\le10000 30
3 k=2k=2
4 k=3k=3

样例 1

输入:

2
7 0 1 0 0 1 0 1
2
1 1
3

输出:

6 0 1 0 0 0 1
0