Xâu Tuyệt Vời
View as PDFBài đang bị tạm khoá, time limit được set rất thấp
Một xâu nhị phân ~t~ được gọi là tuyệt vời nếu đồng thời thỏa mãn 2 điều kiện sau đây:
Tồn tại ít nhất một ký tự 1 trong xâu
Độ dài của xâu ~t~ chia hết cho số lượng ký tự 1 trong xâu. Ví dụ: 1, 1010, 111 đều là các xâu tuyệt vời; còn 0, 110, 01010 thì không.
Cho xâu nhị phân ~s~, đếm số lượng xâu con của ~s~ là xâu tuyệt vời.
Xâu ~a~ được gọi là xâu con của xâu ~b~ khi xóa đi một vài ký tự (có thể là ~0~) ở đầu và một vài ký tự (có thể là ~0~) ở cuối xâu ~b~ thì có được xâu ~a~.
Input
Gồm một dòng duy nhất chứa xâu nhị phân ~s~ (~1\leq |s|\leq 100\ 000~) chỉ bao gồm các ký tự 0 và 1.
Output
Gồm một dòng duy nhất chứa số nguyên dương là số xâu con tuyệt vời của ~s~.
Sample Input 1
111
Sample Output 1
6
Sample Input 2
01010
Sample Output 2
10
Sample Input 3
0000
Sample Output 3
0
Sample Input 4
1111100000
Sample Output 4
25
Notes
Trong ví dụ đầu tiên, tất cả xâu con của ~s~ đều tuyệt vời.
Trong ví dụ thứ hai, các xâu con tuyệt vời của ~s~ là: 1 (~2~ lần), 01 (~2~ lần), 10 (~2~ lần), 010 (~2~ lần), 1010, 0101.
Trong ví dụ thứ ba, không có xâu con nào tuyệt vời.
Comments
This comment is hidden due to too much negative feedback. Show it anyway.