← 返回题目列表

AtCoder · awc0093_e

E. 团队划分的一致性

中文机器翻译题面 查看原题

分数: 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