306917: CF1270F. Awesome Substrings
Memory Limit:512 MB
Time Limit:8 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Awesome Substrings
题意翻译
- 给定一个长度为 $n$ 的 $01$ 串 $s$。 - 求有多少个区间 $[l,r]$ 满足 $r - l + 1$ 是 $s_{l\dots r}$ 中 $1$ 的个数的倍数。 - $n \le 2 \times 10^5$。题目描述
Let's call a binary string $ s $ awesome, if it has at least $ 1 $ symbol 1 and length of the string is divisible by the number of 1 in it. In particular, 1, 1010, 111 are awesome, but 0, 110, 01010 aren't. You are given a binary string $ s $ . Count the number of its awesome substrings. A string $ a $ is a substring of a string $ b $ if $ a $ can be obtained from $ b $ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.输入输出格式
输入格式
The first line contains the string $ s $ ( $ 1 \leq |s|\le 200\,000 $ ) consisting only of zeros and ones.
输出格式
Output a single number — the number of awesome substrings of $ s $ .
输入输出样例
输入样例 #1
111
输出样例 #1
6
输入样例 #2
01010
输出样例 #2
10
输入样例 #3
0000
输出样例 #3
0
输入样例 #4
1111100000
输出样例 #4
25