Awesome Substrings
Contest: Good Bye 2019
Difficulty rating: 2600
Tags: math, strings

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.

Input format:
The first line contains the string $$$s$$$ ($$$1 \leq |s|\le 200\,000$$$) consisting only of zeros and ones.

Output format:
Output a single number — the number of awesome substrings of $$$s$$$.

Constraints:
Time limit: 8.0 s
Memory limit: 512.0 MB

Note:
In the first sample, all substrings of $$$s$$$ are awesome.

In the second sample, we have the following awesome substrings of $$$s$$$: 1 ($$$2$$$ times), 01 ($$$2$$$ times), 10 ($$$2$$$ times), 010 ($$$2$$$ times), 1010, 0101

In the third sample, no substring is awesome.

Example input:
111

Example output:
6

Example input:
01010

Example output:
10

Editorial:
It will be easier for us to think that string is actually an array of ones and zeroes. Let's calculate array of preffix sums  — $$$pref[]$$$. It's easy to see that, substring $$$[l;r]$$$ will be awesome, iff $$$r - l + 1 = k \cdot (pref[r] - pref[l - 1])$$$ for some integer $$$k$$$. It's equivalent to $$$r - k \cdot pref[r] = l - 1 - k \cdot pref[l - 1]$$$. So, we must calculate number of pairs of equal integer in array $$$t[i] = i - k \cdot pref[i]$$$ for each $$$k$$$ from $$$1$$$ to $$$n$$$. Let's fix some number $$$T$$$ and note, that if $$$k > T$$$, then $$$pref[r] - pref[l - 1] = \frac{r - l + 1}{k} \le \frac{n}{T}$$$. In other words, in awesome substring number of ones or $$$k$$$ is not big. For $$$k \le T$$$ we can calculate number of pairs of equal integers in $$$O(nT)$$$. To do this, note that $$$-nT \le i - k \cdot pref[i] \le n$$$, so, independently for each $$$k$$$ we can put all numbers into one array and then calculate number of equal integers. After this, we can fix $$$l$$$ and iterate how many number of ones our string will contain(using this, we get bounds for $$$r$$$). Knowing number of ones, we'll know which remainder should give $$$r$$$. So, task comes down to calculate how many integeres on some segment give some fixed remainder if we divide them by some fixed integer. This can be calculated in constant time(but you should remember to count only such $$$r$$$ for whic $$$k > T$$$. This part works in $$$O(n \cdot \frac{n}{T})$$$. If we choose $$$T = \sqrt{n}$$$,we will get that our solution works in $$$O(n\sqrt{n})$$$(on practice, this solution easily fits in TL for $$$T$$$ from $$$300$$$ to $$$500$$$)
Also note, that if you use some data structures for the first part(like map or unordered_map in C++) and choose big $$$T$$$, your solution can get TL. TL wasn't big because of fast bruteforces.
P.S. I'm writing this one day before round and hope [user:MrDindows] will solve this task without bruteforce.