[ABC295D] Three Days Ago

题意翻译

给出一个数字串，问有多少子段满足，可以以某种方式将这个子段重排，将子段分成两个完全相同的部分。

题目描述

[problemUrl]: https://atcoder.jp/contests/abc295/tasks/abc295_d `20230322` は並べ替えると `02320232` となり、これは `0232` を $ 2 $ 度繰り返しています。このように、数字のみからなる文字列であって、適切に文字を並び替える (そのままでもよい) ことによって同じ列を $ 2 $ 度繰り返すようにできるものを **嬉しい列** と呼びます。数字のみからなる文字列 $ S $ が与えられるので、以下の条件を全て満たす整数の組 $ (l,r) $ はいくつあるか求めてください。 - $ 1\ \le\ l\ \le\ r\ \le\ |S| $ ( $ |S| $ は $ S $ の長さ) - $ S $ の $ l $ 文字目から $ r $ 文字目までの (連続する) 部分文字列は嬉しい列である。

输入输出格式

输入格式

入力は以下の形式で標準入力から与えられる。 > $ S $

输出格式

答えを整数として出力せよ。

输入输出样例

输入样例 #1

20230322

输出样例 #1

输入样例 #2

0112223333444445555556666666777777778888888889999999999

输出样例 #2

输入样例 #3

3141592653589793238462643383279502884197169399375105820974944

输出样例 #3

说明

### 制約 - $ S $ は数字のみからなる長さ $ 1 $ 以上 $ 5\ \times\ 10^5 $ 以下の文字列 ### Sample Explanation 1 $ S= $ `20230322` です。条件を満たす整数組 $ (l,r) $ は $ (1,6),(1,8),(2,7),(7,8) $ の $ 4 $ つです。 ### Sample Explanation 2 $ S $ の先頭が `0` である場合もあります。