← 返回题目列表

AtCoder · abc295_d

G. 三天前

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

分数: 400 点

问题陈述

字符串 20230322 可以重新排列为 02320232,这是重复 0232 两次。
类似地,由数字组成的字符串被称为 快乐 当它可以重新排列为(或已经是)某个字符串的重复两次时。
给你一个字符串 S 由数字组成。查找整数对的数量 (l,r) 满足以下所有条件。

  • 1 \le l \le r \le |S|. (|S| 是长度 S.)
  • 由以下组成的(连续)子字符串 l-th 通过 r- 第一个字符 S 很高兴。

约束

  • S 是由数字组成的字符串,其长度介于 1 和 5 \times 10^5,包括在内。

输入

输入由标准输入按以下格式给出:

S

输出

打印一个代表答案的整数。


样本输入 1

20230322

示例输出 1

4

我们有 S= 20230322.

这是四对整数 (l,r) 满足条件: (1,6), (1,8), (2,7),和 (7,8).


示例输入 2

0112223333444445555556666666777777778888888889999999999

示例输出 2

185

S 可能以 0.


示例输入 3

3141592653589793238462643383279502884197169399375105820974944

示例输出 3

9