2458 「POI2010」01 序列计数 Ones

译自 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$ 是一个正整数，$x_2$ 是其二进制表示（最高位为 1），则该数的压缩形式 $REP(x)$ 为一个序列，表示连续相同数位的数量。例如： $$ REP(460288) = REP(1110000011000000000_2) = (3,5,2,9) $$ $$ REP(408) = REP(110011000_2) = (2,2,2,3) $$

已知 $REP(n)$，求 $REP(sks(n))$。

第一行有一个整数 $k$ ，表示一个正整数 $n$ 的压缩形式。 接下来一行有 $k$ 个整数 $x_1, x_2, ..., x_k$ ，用空格分隔，表示 $n$ 的压缩形式序列。保证 $x_1 + x_2 + ... + x_k \le 1000000000$，也就是说 $0 \lt n \lt 2^{1000000000}$。

输出两行，第一行有一个正整数 $l$，第二行有 $l$ 个正整数 $y_1, y_2, ..., y_l$，用空格分隔，表示 $sks(n)$ 的压缩形式。

序列 $1,1,1,1,1,1$ 为 $101010_2 = 42$ 的压缩形式，$sks(42) = 45$，而 $45 = 101101_2$ 的压缩形式为 $1,1,2,1,1$.

对于 $100\%$ 的数据， $1 \le k \le 1000000 , 0 \lt x_i \le 1000000000$ 。

Translated by vincent163