#P6934. ⽪卡丘
⽪卡丘
题目描述
最初有一棵只有根节点的二叉树。每经过一秒,每个已有节点会补齐缺失的左、右儿子。新产生的节点从下一秒起才产生儿子。
需要依次执行两种操作。
G T:让时间前进 秒。A S:从根节点按非空字符串 移动。L表示走向左儿子,R表示走向右儿子。保证路径上的节点都存在。删除最终到达的节点及其整棵子树。此操作不推进时间。
对每个操作,输出操作完成后的树上节点数对 取模的结果。
输入格式
第一行一个整数 ,表示数据组数。
每组先输入一行一个整数 ,表示操作数。接下来 行,每行为 G T 或 A S。
输出格式
每次操作后输出一行一个整数,按输入次序共输出 行。
样例
2
6
G 1
A L
G 1
A R
G 1
G 1
3
G 3
A LR
A RRR
3
2
5
2
5
11
15
12
11
数据范围
对于全部数据,,,。这些求和覆盖整个输入。若没有攻击操作,则 。
| 原题数据占比 | 附加限制 |
|---|---|
| 前 20% | ,每组 $1\le n,\sum |
| 另有 10% | 只有 G 操作 |
| 每组内任一攻击路径 都不是另一条攻击路径的前缀 | |
| 另有 30% | ,$\sum |
原题时间限制 1 秒,内存限制 512 MB。