CF2092F Andryusha and CCB

我们定义一个二进制字符串 $z$ 的**美感值**为满足 $1 \le i < |z|$ 且 $z_i \neq z_{i+1}$ 的索引 $i$ 的数量。 在等待 CCB 的朋友们到来时，Andryusha 烤了一个馅饼，表示为一个长度为 $n$ 的二进制字符串 $s$。为了避免冒犯任何人，他想要将这个字符串分割成 $k$ 个子字符串，使得每个字符属于恰好一个子字符串，且所有子字符串的美感值相同。 Andryusha 不知道会有多少 CCB 的朋友来他家，因此他希望找出满足条件的所有 $k$ 值的数量。然而，他的兄弟 Tristan 认为这个问题的表述过于简单。因此，他要求你为字符串的每个前缀找出这样的 $k$ 值的数量。换句话说，对于每个 $i$（从 $1$ 到 $n$），你需要找出满足可以将前缀 $s_1 s_2 \ldots s_i$ 分割成恰好 $k$ 个具有相同美感值的子字符串的 $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$) —— 表示对于前缀 $s_1 s_2 \ldots s_i$ 满足条件的 $k$ 值的数量。

第三个测试案例中，满足条件的 $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\}$。 翻译由 DeepSeek R1 完成