CSES - Bit Substrings | Xâu con nhị phân

View as PDF



Author:
Problem type
Points: 1600 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

You are given a bit string of length \(n\). Your task is to calculate for each k between \(0…n\) the number of non-empty substrings that contain exactly \(k\) ones.

For example, if the string is 101, there are:

  • \(1\) substring that contains \(0\) ones: 0
  • \(4\) substrings that contain \(1\) one: 01, 1, 1, 10
  • \(1\) substring that contains \(2\) ones: 101
  • \(0\) substrings that contain \(3\) ones

Input

  • The only input line contains a binary string of length \(n\).

Output

  • Print \(n+1\) values as specified above.

Constraints

  • \(1\leq n \leq 2 ⋅ 10^5\)

Example

Sample input

101

Sample output

1 4 1 0

Comments


  • 1
    vanphukhang_0604    8:33 p.m. 14 aug, 2023 edit 3

    CSES - Bit Substrings | Xâu con nhị phân

    Cho một xâu nhị phân độ dài \(n\). Với mỗi số nguyên \(k\) từ \(0,\ldots,n\), hãy tính số xâu con không rỗng của xâu đã cho sao cho mỗi xâu con có chứa đúng \(k\) số \(1\).

    Ví dụ, với xâu 101, có:

    • \(1\) xâu con chứa \(0\) số \(1\): 0
    • \(4\) xâu con chứa \(1\) số \(1\): 01, 1, 1, 10
    • \(1\) xâu con chứa \(2\) số \(1\): 101
    • \(0\) xâu con chứa \(3\) số \(1\)

    Input

    • Dòng duy nhất chứa xâu nhị phân độ dài \(n \ (1 \leq n \leq 2 \cdot 10^5)\).

    Output

    • Một dòng chứa \(n+1\) giá trị được chỉ định trên đề bài.

    Example

    Test 1

    Input
    101
    Output
    1 4 1 0