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$

输出格式

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

输入输出样例 #1

输入 #1

20230322

输出 #1

4

输入输出样例 #2

输入 #2

0112223333444445555556666666777777778888888889999999999

输出 #2

185

输入输出样例 #3

输入 #3

3141592653589793238462643383279502884197169399375105820974944

输出 #3

9

说明/提示

限制条件

• $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 翻译