三天前

题目描述

字符串 20230322 可以重新排列成 02320232，这是把 0232 重复两次得到的字符串。

类似地，当一个由数字组成的字符串可以重新排列成（或已经是）某个字符串重复两次得到的字符串时，称它是快乐的（happy）。

给定一个由数字组成的字符串 $S$。求满足以下所有条件的整数对 $(l,r)$ 的个数。

• $1 \le l \le r \le |S|$。（$|S|$ 是 $S$ 的长度。）
• 由 $S$ 的第 $l$ 个到第 $r$ 个字符组成的（连续）子串是快乐的。

输入格式

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

$S$

输出格式

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

样例

20230322

4

有 $S=$ 20230322。 满足条件的整数对 $(l,r)$ 有以下 4 个：$(1,6)$、$(1,8)$、$(2,7)$、$(7,8)$。

0112223333444445555556666666777777778888888889999999999

185

$S$ 可能以 0 开头。

3141592653589793238462643383279502884197169399375105820974944

9

数据范围

• $S$ 是由数字组成的字符串，其长度介于 $1$ 和 $5 \times 10^5$ 之间（含两端）。