← 返回题目列表

AtCoder · aising2020_d

D. 一切归零

中文机器翻译题面 查看原题

分数: 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