分数: 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