← 返回题目列表

AtCoder · arc033_1

A. 隐藏的话

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

問題文

高桥喜欢玩寻找隐藏单词的游戏。例如,“黄瓜”一词隐藏在“jikyuryoku”中。

高桥君现在长高了 我正在尝试查找字符串 N 中的隐藏单词。为了枚举隐藏的候选单词,我决定首先计算该字符串中“子字符串”的数量。

文字列 S 的“子字符串”是一个字符串 S 中包含的某个区间中提取的字符串。例如,“Snuke”的子串是“su”、“nu”、“ke”、“sunu”、“nuke”、“snuke”。 6 一。请注意,“suke”和“nusu”等单词不是子字符串。

另外,字符串 S 具有相同的字符 众所周知,它出现的次数不会超过 2 次。因此,从不同位置提取的字符串,例如“shobosho”中的“sho”,永远不会匹配。


入力

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

N
  • 1 行包含一个表示字符串长度的整数。 字符串 N (1 ≦ N ≦ 1000) 。 表示

出力

长度 小于或等于 N 中“子字符串”的数量 在 1 行输出。在输出末尾插入换行符。


入力例1

1

出力例1

1

入力例2

2

出力例2

3

入力例3

3

出力例3

6

如问题中“Snuke”的例子所示, 有6 子字符串。


入力例4

4

出力例4

10