题目描述
译自 POI 2010 Stage 3. Day 2「Ones」
设 x 是一个由 01 组成的序列。一个 UFO 指的是序列中第一个 1 或者最后一个 1 且不和任何一个 1 相邻。例如 10001010 有两个 UFO,1101011000 没有 UFO,1000 只有一个 UFO。
设 1 到 n 的数的二进制表示中 UFO 的总数为 sks(n)。例如,sks(5)=5,sks(64)=59,sks(128)=122,sks(256)=249。
我们需要处理非常大的数字。因此 n 会用压缩的形式表示。设 x 是一个正整数,x2 是其二进制表示(最高位为 1),则该数的压缩形式 REP(x) 为一个序列,表示连续相同数位的数量。例如:
REP(460288)=REP(11100000110000000002)=(3,5,2,9)
REP(408)=REP(1100110002)=(2,2,2,3)
已知 REP(n),求 REP(sks(n))。
输入格式
第一行有一个整数 k ,表示一个正整数 n 的压缩形式。
接下来一行有 k 个整数 x1,x2,...,xk ,用空格分隔,表示 n 的压缩形式序列。保证 x1+x2+...+xk≤1000000000,也就是说 0<n<21000000000。
输出格式
输出两行,第一行有一个正整数 l,第二行有 l 个正整数 y1,y2,...,yl,用空格分隔,表示 sks(n) 的压缩形式。
样例
6
1 1 1 1 1 1
5
1 1 2 1 1
序列 1,1,1,1,1,1 为 1010102=42 的压缩形式,sks(42)=45,而 45=1011012 的压缩形式为 1,1,2,1,1.
数据范围与提示
对于 100% 的数据, 1≤k≤1000000,0<xi≤1000000000 。
Translated by vincent163