#PQJ222x4103. QOJ 222_4103

    ID: 2781 传统题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SDOI 2016

QOJ 222_4103

生成魔咒 【问题描述】 魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示。例如可以将魔咒字 符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≤n≤10。 对于30%的数据,1≤n≤100。 对于60%的数据,1≤n≤1000。 对于100%的数据,1≤n≤100000。 用来表示魔咒字符的数字x 满足 9 10 1  x 。