4062: 「SDOI2016」生成魔咒
内存限制:256 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:0
解决:0
题目描述
魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示。例如可以将魔咒字符 $ 1 $、$ 2 $ 拼凑起来形成一个魔咒串 $ [1, 2] $。
一个魔咒串 $ S $ 的非空子串被称为魔咒串 $ S $ 的生成魔咒。
例如 $ S = [1, 2, 1] $ 时,它的生成魔咒有 $ [1] $、$ [2] $、$ [1, 2] $、$ [2, 1] $、$ [1, 2, 1] $ 五种。$ S = [1, 1, 1] $ 时,它的生成魔咒有 $ [1] $、$ [1, 1] $、$ [1, 1, 1] $ 三种。
最初 $ S $ 为空串。共进行 $ n $ 次操作,每次操作是在 $ S $ 的结尾加入一个魔咒字符。每次操作后都需要求出,当前的魔咒串 $ S $ 共有多少种生成魔咒。
输入
第一行一个整数 $ n $。
第二行 $ n $ 个数,第 $ i $ 个数表示第 $ i $ 次操作加入的魔咒字符。
输出
输出 $ n $ 行,每行一个数。第 $ i $ 行的数表示第 $ i $ 次操作后 $ S $ 的生成魔咒数量。
样例输入 复制
7
1 2 3 3 3 1 2
样例输出 复制
1
3
6
9
12
17
22
提示
数据范围:对于 $ 10\% $ 的数据,$ 1 \leq n \leq 10 $; 对于 $ 30\% $ 的数据,$ 1 \leq n \leq 100 $; 对于 $ 60\% $ 的数据,$ 1 \leq n \leq 1000 $; 对于 $ 100\% $ 的数据,$ 1 \leq n \leq 100000 $。 用来表示魔咒字符的数字 $ x $ 满足 $ 1 \leq x \leq 10 ^ 9 $。