子串分值

【问题描述】

对于一个字符串 S，我们定义 S 的分值 f (S ) 为 S 中出现的不同的字符个 数。例如 f (”aba”) = 2， f (”abc”) = 3, f (”aaa”) = 1。 现在给定一个字符串 S [0::n − 1]（长度为 n），请你计算对于所有 S 的非空 子串 S [i:: j](0 ≤ i ≤ j < n)， f (S [i:: j]) 的和是多少。

【输入格式】

输入一行包含一个由小写字母组成的字符串S。

【输出格式】

输出一个整数表示答案。

【样例输入】

ababc
1

【样例输出】

28
1

【样例说明】

子串 f值
a 1
ab 2
aba 2
abab 2
ababc 3
b 1
ba 2
bab 2
babc 3
a 1
ab 2
abc 3
b 1
bc 2
c 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

【评测用例规模与约定】

对于20% 的评测用例，1 ≤ n ≤ 10； 对于40% 的评测用例，1 ≤ n ≤ 100； 对于50% 的评测用例，1 ≤ n ≤ 1000； 对于60% 的评测用例，1 ≤ n ≤ 10000； 对于所有评测用例，1 ≤ n ≤ 100000。 ————————————————

Limitation

1s, 1024KiB for each test case.