← 返回题目列表

Codeforces · 1168/B

B. 好三重

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

Toad Rash 有一个二进制字符串 $$$s$$$。二进制字符串仅由零和一组成。

令 $$$n$$$ 为 $$$s$$$ 的长度。

Rash 需要找到这样的整数对 $$$l$$$, $$$r$$$ 的数量,使得 $$$1 \leq l \leq r \leq n$$$ 并且至少有一对整数 $$$x$$$, $$$k$$$ 使得 $$$1 \leq x, k \leq n$$$, $$$l \leq x < x + 2k \leq r$$$,并且 $$$s_x = s_{x+k} = s_{x+2k}$$$。

找出 Rash 的配对数。

输入

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

输出

输出一个整数:$$$1 \leq l \leq r \leq n$$$ 的整数对 $$$l$$$, $$$r$$$ 的数量,并且至少有一对整数 $$$x$$$, $$$k$$$ 使得 $$$1 \leq x, k \leq n$$$, $$$l \leq x < x + 2k \leq r$$$,并且 $$$s_x = s_{x+k} = s_{x+2k}$$$。

示例

输入 #1

010101

输出 #1

3

输入 #2

11001100

输出 #2

0

注意

在第一个示例中,我们需要计算三个 $$$l$$$、$$$r$$$ 对:$$$1$$$、$$$6$$$; $$$2$$$、$$$6$$$;和$$$1$$$、$$$5$$$。

在第二个示例中,初始字符串没有值 $$$x$$$、$$$k$$$,因此答案为 $$$0$$$。