SP19288 WPC5C - Sword Game
题目描述
在 2048 年，一个名叫 SSH3 的火星机器人每年都参与银河战争并希望再次获胜。
SSH3 被选中参加一场著名的剑术比赛，这也许是最后一次举行这样的比赛了。比赛的规则如下：
每把剑都有一个名字 $S$，这是由 $n$ 个小写字母组成的字符串。剑的力量决定于以下方法：
定义一个函数 $f(l_1, l_2)$，其中 $1 \le l_1, l_2 \le n$。首先，找到名字 $S$ 中所有长度为 $l_1$ 的子串，确定其中字典序最小的子串，其索引记为 $ind1$。（如有多个字典序最小的子串，就取索引最小的）。
类似地，确定 $ind2$。此时，有 $f(l_1, l_2) = |ind1 - ind2|$。（所有索引从 0 开始）。
剑的强度 $Strength(S)$ 是函数 $f(l_1, l_2)$ 在所有 $l_1, l_2$ 组合下的期望值。
作为一名火星人，SSH3 在数学上应很出色。然而，他来自数学能力普遍不佳的 Quoda 城市，因此恳求你帮助他。请计算并输出 $n^2 \times Strength(S)$ 的值。
输入格式
第一行输入一个整数 $n$，表示剑的名字的字符数量。
第二行输入剑的名字 $S$。
输出格式
输出一个整数，即 $n^2 \times Strength(S)$ 的结果。
说明/提示
- $1 \le n \le 100000$
- $S$ 是由 ‘a’ 到 ‘z’ 的 $n$ 个小写字符组成。
**时间限制**：8 秒。
### 示例：
**输入**：
```
2
ab
```
**输出**：
```
0
```
**解释**：对于每个 $f(l_1, l_2)$，可能的值如下：
- $f(1, 1) = 0$ （$ind1 = 0, ind2 = 0$）
- $f(1, 2) = 0$ （$ind1 = 0, ind2 = 0$）
- $f(2, 1) = 0$ （$ind1 = 0, ind2 = 0$）
- $f(2, 2) = 0$ （$ind1 = 0, ind2 = 0$）
因此，$E(f(l_1, l_2)) = 0$。
最终结果为 $2^2 \times E(f(l_1, l_2)) = 0$。
**本翻译由 AI 自动生成**