AT_abc295_d [ABC295D] Three Days Ago

`20230322` 经过重新排列后可以变为 `02320232`，这是将 `0232` 重复了 $2$ 次。 像这样，只包含数字的字符串，如果通过适当的重新排列（也可以不变），能够变成某个字符串重复 $2$ 次的形式，我们称其为**“开心串”**。 给定一个只包含数字的字符串 $S$，请你求出满足以下所有条件的整数对 $(l, r)$ 的个数。 - $1 \leq l \leq r \leq |S|$（$|S|$ 表示 $S$ 的长度） - $S$ 的第 $l$ 个字符到第 $r$ 个字符组成的（连续的）子串是一个“开心串”。

输入为以下格式，从标准输入读取。 > $S$

请输出满足条件的整数对的个数。

### 限制条件 - $S$ 是一个只包含数字的字符串，长度不少于 $1$，不超过 $5 \times 10^5$。 ### 样例解释 1 $S = $ `20230322`。满足条件的整数对 $(l, r)$ 有 $(1,6), (1,8), (2,7), (7,8)$，共 $4$ 个。 ### 样例解释 2 $S$ 的开头也可能是 `0`。 由 ChatGPT 4.1 翻译