分数: 400 点
问题陈述
让 \mathrm{popcount}(n) 是数量 1s 的二进制表示形式 n。
例如, \mathrm{popcount}(3) = 2, \mathrm{popcount}(7) = 3,和 \mathrm{popcount}(0) = 0.
让 f(n) 是当我们重复以下操作直到 n 变为 0:“替换 n 与余数当 n 除以 \mathrm{popcount}(n).”(可以证明,在本问题的约束下, n 总是变成 0 经过有限次数的操作。)
例如,当 n=7,变成 0 两次操作后,如下:
- \mathrm{popcount}(7)=3,所以我们划分 7 by 3 并将其替换为余数, 1.
- \mathrm{popcount}(1)=1,所以我们划分 1 by 1 并将其替换为余数, 0.
给你一个整数 X 与 N 二进制数字。 对于每个整数 i 这样 1 \leq i \leq N,让 X_i 是什么 X 变为当 i从顶部开始的第 位被反转。 查找 f(X_1), f(X_2), \ldots, f(X_N).
约束
- 1 \leq N \leq 2 \times 10^5
- X 是一个整数 N 二进制数字,可能带有前导零。
输入
输入由标准输入按以下格式给出:
N X
输出
打印 N 行。的 i- 第行应包含该值 f(X_i).
示例输入 1
3 011
示例输出 1
2 1 1
- X_1 = 7,将更改如下: 7 \rightarrow 1 \rightarrow 0因此, f(7) = 2.
- X_2 = 1,将更改如下: 1 \rightarrow 0因此, f(1) = 1.
- X_3 = 2,将更改如下: 2 \rightarrow 0因此, f(2) = 1.
示例输入 2
23 00110111001011011001110
示例输出 2
2 1 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 3