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
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ó:001,1,1,10101Input
Output
Example
Test 1
Input
Output