← 返回题目列表

Codeforces · 1270/F

F. 很棒的子串

中文机器翻译题面 查看原题

如果一个二进制字符串 $$$s$$$ 至少有 $$$1$$$ 符号 1 并且字符串的长度可以被其中 1 的个数整除,那么我们称它为“awesome”。特别是,1、1010、111 很棒,但 0、110、01010 则不然。

给你一个二进制字符串$$$s$$$。计算它的精彩子串的数量。

字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。

输入

第一行包含字符串 $$$s$$$ ($$$1 \leq |s|\le 200\,000$$$) 仅由零和一组成。

输出

输出一个数字——$$$s$$$ 的令人敬畏的子字符串的数量。

示例

输入 #1

111

输出 #1

6

输入 #2

01010

输出 #2

10

输入 #3

0000

输出 #3

0

输入#4

1111100000

输出#4

25

注意

在第一个示例中,$$$s$$$ 的所有子字符串都很棒。

在第二个示例中,我们有以下很棒的 $$$s$$$ 子字符串:1($$$2$$$ 次)、01($$$2$$$ 次)、10($$$2$$$ 次)、010($$$2$$$ 次)、1010、0101

在第三个示例中,没有子字符串是很棒的。