← 返回题目列表

AtCoder · utpc2023_n

N. 缩写数量

中文机器翻译题面 查看原题

配点 : 100 点

問題文

由小写英文字母组成的长度 N 的字符串 S=S_1 S_2 \dots S_N 存在。以下操作恰好进行 1 次时,请求最后可能出现的 S 字符串种类数。

  • 1 \le l \le r \le N 的整数 选择 l, r ,S 可以得到第 l 从第一个字符开始 r 移除到第几个字符为止。也就是说,操作之后 S 是 您也可以写 S_1S_2\dots S_{l-1}S_{r+1}\dots S_N 变为。

制約

  • N 是一个整数
  • 1 \leq N \leq 5 \times 10^5
  • S 是小写字母的长度 N 的字符串

入力

输入是按以下格式从标准输入给出的。

N
S

出力

答案 请打印除以 1 行输出。


入力例 1

5
abbab

出力例 1

11

可以得到 S 如下: 11 是的。 请注意,我们正在寻找除以

  • 空文字列
  • a
  • aab
  • ab
  • abab
  • abb
  • abba
  • abbb
  • b
  • bab
  • bbab

入力例 2

5
aaaaa

出力例 2

5

入力例 3

4
utpc

出力例 3

10