分数: 466 分
问题陈述
有 N 人,我们考虑将他们每个人分配给其中之一 2 团队。任何一支球队都可能是空的。
这个问题涉及 声明。声明已编号 1, 2, \ldots 按添加顺序排列。最初,有 0 声明。每个声明由一对两人组成 (u, v) 为目标,内容 c。内容 c 是其中之一 0 (应在同一团队), 1 (应该在不同的团队中),或者 X (未确定)。那对人 u 和 v 是对称的; (u, v) 和 (v, u) 代表同一对。同一对人可能存在多个声明。
执行 Q 操作按顺序进行。有两种类型的操作:
A u v c(添加操作)
附加针对这两个人的声明 u 和 v 到最后。新增声明内容为 c.
R k(传播操作)
阅读 当前内容 声明的 声明的 k,和 覆盖 申报内容 k+1 与通过添加获得的值 1 到它。申报目标人群 k+1 没有改变。另外,声明的内容 k 没有改变。
这里,加法定义如下: 0 + 1 = 1, 1 + 1 = 0, X + 1 = X (尚未确定)。
注意: R 操作可能会更改声明的内容。特别是,如果声明的内容 k is X,申报内容 k+1 被覆盖为 X (即使它最初是 0 or 1)。声明的当前内容取决于截至该点执行的所有操作的历史记录。
每次操作后,确定 好的测定方法 基于所有现有声明及其当前内容,模 998244353。这些术语的定义如下。
测定方法
A 测定方法 是一种独立选择和写入的方法 0 or 1 进入 每个 声明其内容为 X 在所有当前声明中,使所有声明内容要么 0 or 1。已经声明的内容 0 or 1 保持不变。如果两种判定方法在某些声明内容中写入的值不同,则它们是不同的 X。如果有 0 声明内容 X,正是 1 测定方法。
好的测定方法
一种测定方法称为 好的测定方法 如果在使用该方法确定所有申报内容后,存在至少一个同时满足所有申报的团队划分(一种将每个人分配到两个团队之一的方式)。
这里,声明 (u, v, c) 确定内容 (c \in \{0, 1\})是 满意 当:
- If c = 0:人 u 和人 v 属于同一团队
- If c = 1:人 u 和人 v 属于不同的团队
补充(图论改写): 考虑一个多重图,其中每个人都是一个顶点,每个声明都是一条边(没有自循环,因为 u \neq v)。确定后,每条边的权重为 0 or 1。同时满足所有声明的团队划分存在的充分必要条件是,该图中沿每个周期的边权重的异或为 0.
约束
- 2 \leq N \leq 3000
- 1 \leq Q \leq 3000
- In
A u v c, 1 \leq u, v \leq N 和 u \neq v - In
A u v c, c 是其中之一0,1,X - In
R k,让 M 是该操作时的声明总数, 1 \leq k \leq M - 1 (保证两个声明 k 和声明 k+1 存在) - 所有操作的声明总数(A 操作的数量)最多为 Q
- R 操作不添加或删除声明
- N, Q, u, v, k 是整数
输入
N Q query_1 query_2 \vdots query_Q
- 第一行包含一个整数 N 代表人数和一个整数 Q 代表操作次数,以空格分隔。
- 以下 Q 行给出操作 query_i 采用以下格式之一:
A u v c- 添加针对这两个人的声明 u 和 v.
- c 是其中之一
0,1,X. R k- 覆盖声明内容 k+1 与通过添加获得的值 1 至当前声明内容 k.
输出
输出 Q 行。
关于 i第行,输出紧随其后的良好测定方法的数量 i-次运算,模数 998244353.
示例输入 1
3 5 A 1 2 0 A 2 3 X A 1 3 1 R 2 R 1
示例输出 1
1 2 1 2 1
示例输入 2
3 6 A 1 2 0 A 2 3 0 A 1 3 1 A 1 3 X R 3 R 1
示例输出 2
1 1 0 0 0 0
示例输入 3
7 15 A 1 2 X A 2 3 0 A 3 4 1 A 4 5 X A 5 1 0 R 1 A 2 5 1 R 5 A 6 7 X A 1 7 1 R 7 A 3 6 0 R 8 R 3 A 2 4 X
示例输出 3
2 2 2 4 2 4 2 2 4 4 8 4 8 4 4
示例输入 4
12 30 A 1 2 0 A 2 3 X A 3 4 1 A 4 5 0 A 5 6 X A 6 1 1 R 2 A 7 8 0 A 8 9 X A 9 10 1 A 10 11 0 A 11 12 X A 12 7 1 R 8 R 11 A 1 7 X A 3 9 0 R 12 A 5 11 1 R 14 A 2 8 X A 4 10 0 R 16 A 6 12 1 R 17 R 1 R 3 A 1 12 X R 18 A 2 11 0
示例输出 4
1 2 2 2 4 2 4 4 8 8 8 16 8 16 32 64 32 32 16 16 16 0 16 8 16 8 16 16 16 8
示例输入 5
2 1 A 1 2 X
示例输出 5
2