7450. 二进制子串 (Bit Substrings)
时间限制：1000 MS 内存限制：512 MB
题目描述
# 二进制子串 (Bit Substrings) 时间限制：$1.00\text{ s}$ 空间限制：$512\text{ MB}$ ## 题目描述 给你一个长度为 $n$ 的 01 字符串。你的任务是，对于每一个 $k \in [0, n]$，计算含有恰好 $k$ 个字符 `1` 的非空连续子串的数量。 例如，对于字符串 `101`： - 包含 $0$ 个 `1` 的非空连续子串有 $1$ 个：`0`。 - 包含 $1$ 个 `1` 的非空连续子串有 $4$ 个：`01`、`1`（第一个位置）、`1`（第三个位置）、`10`。 - 包含 $2$ 个 `1` 的非空连续子串有 $1$ 个：`101`。 - 包含 $3$ 个 `1` 的非空连续子串有 $0$ 个。 ## 输入格式 唯一的一行输入包含一个长度为 $n$ 的二进制字符串。 ## 输出格式 输出 $n+1$ 个值，分别对应 $k = 0, 1, \dots, n$ 的结果，用空格分隔。 ## 输入输出样例 ### 输入 #1 ```text 101 ``` ### 输出 #1 ```text 1 4 1 0 ``` ## 说明/提示 ### 数据规模与约定 - $1 \le n \le 2 \cdot 10^5$