← 返回题目列表

Codeforces · 2092/F

F. Andryusha 和 CCB

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

让我们定义 美女 二进制字符串 $$$z$$$ 的 作为索引 $$$i$$$ 的数量,使得 $$$1 \le i \lt |z|$$$ 和 $$$z_i \neq z_{i+1}$$$。

在等待来自 CCB 的朋友时,Andryusha 烤了一个馅饼,由长度为 $$$n$$$ 的二进制字符串 $$$s$$$ 表示。为了避免得罪任何人,他想把这个字符串分成 $$$k$$$ 个子字符串,使得每个数字都属于一个子字符串,并且所有子字符串的美感都是相同的。

Andryusha 不知道 CCB 的朋友会来他家的确切数量,因此他想找到 $$$k$$$ 的值的数量,从而可以将馅饼分割成具有相同美感的 $$$k$$$ 部分。

然而,Andryusha 的兄弟 Tristan 认为这个问题的表述过于简单。因此,他希望你找到$$$k$$$这样的值的个数 对于字符串的每个前缀。换句话说,对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,您需要找到 $$$k$$$ 的值的数量,对于这些值,可以将前缀 $$$s_1 s_2 \ldots s_i$$$ 拆分为具有相同美感的 $$$k$$$ 部分。

输入

每个测试由多个测试用例组成。输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — 二进制字符串的长度。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串,仅由数字组成 0 和 1.

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,输出一行包含 $$$n$$$ 整数 $$$c_i$$$ ($$$0 \le c_i \le n$$$) — $$$k$$$ 的值的数量,可以将前缀 $$$s_1 s_2 \ldots s_i$$$ 拆分为具有相同美感的 $$$k$$$ 部分。

示例

输入
复制

3
5
00011
10
0101010101
7
0010100

输出
复制

1 2 3 4 5
1 2 2 3 2 4 2 4 3 4
1 2 3 3 4 3 4

注意

第三种情况,满足条件的$$$k$$$的值为:

  1. $$$i = 1$$$: $$$k \in \{1\}$$$,
  2. $$$i = 2$$$: $$$k \in \{1, 2\}$$$,
  3. $$$i = 3$$$: $$$k \in \{1, 2, 3\}$$$,
  4. $$$i = 4$$$: $$$k \in \{1, 3, 4\}$$$,
  5. $$$i = 5$$$: $$$k \in \{1, 2, 4, 5\}$$$,
  6. $$$i = 6$$$: $$$k \in \{1, 5, 6\}$$$,
  7. $$$i = 7$$$: $$$k \in \{1, 5, 6, 7\}$$$。