P4070 [SDOI2016]生成魔咒

    • 622通过
    • 1.1K提交
  • 题目提供者 ElevenDimensions
  • 评测方式 云端评测
  • 标签 后缀数组,SA 字符串 平衡树 各省省选 2016 山东
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示。例如可以将魔咒字符 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 的生成魔咒数量

    输入输出样例

    输入样例#1: 复制
    7
    1 2 3 3 3 1 2
    输出样例#1: 复制
    1
    3
    6
    9
    12
    17
    22

    说明

    对于%10的数据,$1 \le n \le 10$

    对于%30的数据,$1 \le n \le 100$

    对于%60的数据,$1 \le n \le 100$

    对于%100的数据,$1 \le n \le 100000$

    用来表示魔咒字符的数字 x 满足$1 \le n \le 10^9$

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。