#PQJ222x4103. QOJ 222_4103
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 。