当前没有测试数据。

D - 三天之前

得分 : $400$ 分

问题描述

字符串20230322可以重新排列成02320232，它是0232的两次重复。
类似地，如果一个由数字组成的字符串可以被重新排列成（或已经是）某个字符串的两次重复，则称其为happy。
给定一个由数字组成的字符串 $S$。找到满足以下所有条件的整数对$(l,r)$的数量。

• $1 \le l \le r \le |S|$. （$|S|$是$S$的长度。）
• $S$的第$l$到$r$个字符（连续子串）是happy的。

约束条件

• $S$是由数字组成的字符串，长度在 $1$ 和 $5 \times 10^5$ 之间，包括边界值。

输入

从标准输入中以以下格式给出：

$S$

输出

输出一个表示答案的整数。

20230322

4

我们有$S=$ 20230322。

以下四个整数对满足条件：$(1,6)$，$(1,8)$，$(2,7)$，和$(7,8)$。

0112223333444445555556666666777777778888888889999999999

185

$S$ 可以以0 开头。

3141592653589793238462643383279502884197169399375105820974944

9