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

Xem PDF

Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một chuỗi bit có độ dài \(n\). Với mỗi \(k\) từ \(0 ... n\), tính số chuỗi không rỗng có chứa đúng \(k\) số \(1\).

Ví dụ, nếu chuỗi là 101, có:

  • \(1\) chuỗi con chứa \(0\) số \(1\): 0
  • \(4\) chuỗi con chứa \(1\) số \(1\): 01, 1, 1, 10
  • \(1\) chuỗi con chứa \(2\) số \(1\): 101
  • \(0\) chuỗi con chứa \(3\) số \(1\)

Input

  • Dòng duy nhất chứa chuỗi nhị phân độ dài \(n\).

Output

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

Constraints

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

Example

Sample input

101

Sample output
1 4 1 0


Bình luận


  • 0
    vanphukhang_0604    8:33 p.m. 14 Tháng 8, 2023 chỉnh sửa 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