P5287 [HNOI2019]JOJO

    • 101通过
    • 479提交
  • 题目提供者 chen_zhe Aya
  • 评测方式 云端评测
  • 标签 各省省选 2019 湖南
  • 难度 省选/NOI-
  • 时空限制 1000ms / 512MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    JOJO 的奇幻冒险是一部非常火的漫画。漫画中的男主角经常喜欢连续喊很多的“欧拉”或者“木大”。

    题目描述

    为了防止字太多挡住漫画内容,现在打算在新的漫画中用 $x$ 欧拉或者 $x$ 木大表示有 $x$ 个欧拉或者木大。

    为了简化内容我们现在用字母表示喊出的话。

    我们用数字和字母来表示一个串,例如: 2 a 3 b 表示的串就是 $aabbb$。

    一开始漫画中什么话都没有,接下来你需要依次实现 $n$ 个操作,总共只有 $2$ 种操作:

    第一种:1 x c 在当前漫画中加入 $x$ 个 $c$ (表示在当前串末尾加入 $x$ 个 $c$ 字符。)(保证当前串是空串或者串尾字符不是 $c$)

    第二种:2 x 觉得漫画没画好将漫画还原到第 $x$ 次操作以后的样子(表示将串复原到第 $x$ 次操作后的样子,如果 $x=0$ 则是将串变成空串。)

    (如果当前串是 $bbaabbb$,第 $4$ 次操作后串是 $bb$,则 2 4 会使$bbaabbb$ 变成 $bb$, 保证 $x$ 小于当前操作数)

    众所周知空条承太郎十分聪明,现在迪奥已经被打败了,他开始考虑自己的漫画中的一些问题:

    对于一个串的每个前缀 $A$,都有一个最长的比它短的前缀 $B$ 与前缀 $A$ 的一个后缀匹配,设这个最长的前缀 $B$ 的长度为 $L$。$L$ 为 $0$ 时意味着 $B$ 是一个空串。

    每一次操作后,你都需要将当前的串的所有前缀的 $L$ 求和并对 $998244353$ 取模输出告诉空条承太郎,好和他的白金之星算出的答案对比。

    比如 $bbaaabba$ 的 $L$ 分别是:0 1 0 0 0 1 2 3,所以对于这个串的答案就是 $7$。

    输入输出格式

    输入格式:

    第一行包括一个正整数$n$,表示操作数量。

    接下来$n$行每行包含一个操作,操作格式如题面所示,例如:

    1 x c

    2 x

    保证数据合法。

    输出格式:

    输出文件仅包含 $n$ 行,第 $i$ 行一个整数,表示 $i$ 个操作之后串的答案。

    输入输出样例

    输入样例#1: 复制
    11
    1 2 a
    1 3 b
    1 2 a
    1 1 b
    2 2
    1 3 a
    1 2 b
    2 6
    2 5
    1 7 a
    1 5 c
    
    输出样例#1: 复制
    1
    1
    4
    7
    1
    6
    13
    6
    1
    14
    14
    

    说明

    样例解释

    $1:aa \;0+1=1$

    $2:aabbb \;0+1+0+0+0=1$

    $3:aabbbaa \;0+1+0+0+0+1+2=4$

    $4:aabbbaab \;0+1+0+0+0+1+2+3=7$

    $5:aabbb \;0+1+0+0+0=1$

    $6:aabbbaaa \;0+1+0+0+0+1+2+2=6$

    $7:aabbbaaabb \;0+1+0+0+0+1+2+2+3+4=13$

    $8:aabbbaaa \;0+1+0+0+0+1+2+2=6$

    $9:aabbb \;0+1+0+0+0=1$

    $10:aabbbaaaaaaa \;0+1+0+0+0+1+2+2+2+2+2+2=14$

    $11:aabbbaaaaaaaccccc \;0+1+0+0+0+1+2+2+2+2+2+2+0+0+0+0+0=14$

    对于前 10 个点

    20%的数据满足$n\leq 300$对于每个$1$操作中的$x\leq 300$;

    另有30%的数据满足$n\leq 100000$且对于每个$1$操作中的$x=1$;

    另有30%的数据满足$n\leq 100000$且不含$2$操作;

    对于所有的点

    100%的数据满足$n\leq 100000$且每个$1$操作中的$x\leq 10000$。

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