E - チーム分けの整合性 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

N 人の人がおり、それぞれを 2 つのチームのいずれかに所属させることを考えます。ただし、どちらか一方のチームが空であっても構いません。

この問題では申告を扱います。申告は追加された順に 1, 2, \ldots と番号が付けられます。はじめ、申告は 0 件です。各申告は、対象となる 2 人の組 (u, v) と、内容 c からなります。内容 c は 0（同じチームに入るべき）、1（異なるチームに入るべき）、または X（未確定）のいずれかです。人 u と人 v の組は対称であり、(u, v) と (v, u) は同じ組を表します。同じ人の組に対して複数の申告が存在することもあります。

Q 回の操作を順に行います。操作は次の 2 種類です。

  • A u v c（追加操作）

人 u と人 v の組を対象とする申告を末尾に追加します。追加される申告の内容は c です。

  • R k（伝搬操作）

申告 k の現在の内容を読み取り、それに 1 を加えた値で申告 k+1 の内容を上書きします。申告 k+1 の対象となる人の組は変化しません。また、申告 k の内容も変化しません。

ここで加算は次のように定義します：0 + 1 = 1、1 + 1 = 0、X + 1 = X（未確定のまま）。

注意： R 操作によって申告の内容は変更されることがあります。特に、申告 k の内容が X の場合、申告 k+1 の内容は（元々 0 や 1 であっても）X に上書きされます。ある申告の現在の内容は、その時点までに行われた全操作の履歴に依存します。

各操作の直後について、その時点で存在する全ての申告とそれらの現在の内容に基づく良い確定方法の個数を 998244353 で割った余りを求めてください。以下で用語を定義します。

確定方法

現在の全ての申告のうち、内容が X であるものそれぞれに 0 または 1 を独立に選んで書き込み、全ての申告の内容を 0 か 1 にする方法を 確定方法 と呼びます。内容が既に 0 や 1 である申告の内容はそのまま変わりません。2 つの確定方法が異なるとは、ある内容 X の申告に対して書き込む値が異なることを意味します。内容が X の申告が 0 件の場合、確定方法はちょうど 1 通りです。

良い確定方法

ある確定方法によって全ての申告の内容を確定させたとき、全ての申告を同時に満たすチーム分け（各人を 2 つのチームのいずれかに割り当てる方法）が少なくとも 1 つ存在するならば、その確定方法を 良い確定方法 と呼びます。

ここで、内容が確定した申告 (u, v, c)（c \in \{0, 1\}）が満たされるとは、次を意味します。

  • c = 0 のとき：人 u と人 v が同じチームに属する
  • c = 1 のとき：人 u と人 v が異なるチームに属する

補足（グラフ理論的な言い換え）： 各人を頂点、各申告を辺とする多重グラフ（u \neq v より自己ループはない）を考えます。確定後の各辺には 0 または 1 の重みが付いています。全ての申告を同時に満たすチーム分けが存在するための必要十分条件は、このグラフの全てのサイクルについて、そのサイクル上の辺の重みの XOR が 0 であることです。

制約

  • 2 \leq N \leq 3000
  • 1 \leq Q \leq 3000
  • A u v c において、1 \leq u, v \leq N かつ u \neq v
  • A u v c において、c は 0、1、X のいずれかである
  • 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
  • 1 行目には、人数を表す整数 N と、操作回数を表す整数 Q が、スペース区切りで与えられる。
  • 続く Q 行では、操作 query_i が次のいずれかの形式で与えられる。
  • A u v c
  • 人 u と人 v の組を対象とする申告を追加する。
  • c は 0、1、X のいずれかである。
  • R k
  • 申告 k の現在の内容に 1 を加えた値で、申告 k+1 の内容を上書きする。

出力

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

Score : 466 pts

Problem Statement

There are N people, and we consider assigning each of them to one of 2 teams. Either team may be empty.

This problem deals with declarations. Declarations are numbered 1, 2, \ldots in the order they are added. Initially, there are 0 declarations. Each declaration consists of a pair of two people (u, v) as the target, and a content c. The content c is one of 0 (should be on the same team), 1 (should be on different teams), or X (undetermined). The pair of people u and v is symmetric; (u, v) and (v, u) represent the same pair. Multiple declarations may exist for the same pair of people.

Perform Q operations in order. There are two types of operations:

  • A u v c (Add operation)

Append a declaration targeting the pair of people u and v to the end. The content of the added declaration is c.

  • R k (Propagate operation)

Read the current content of declaration k, and overwrite the content of declaration k+1 with the value obtained by adding 1 to it. The target pair of people for declaration k+1 does not change. Also, the content of declaration k does not change.

Here, addition is defined as follows: 0 + 1 = 1, 1 + 1 = 0, X + 1 = X (remains undetermined).

Note: The R operation may change the content of a declaration. In particular, if the content of declaration k is X, the content of declaration k+1 is overwritten to X (even if it was originally 0 or 1). The current content of a declaration depends on the history of all operations performed up to that point.

After each operation, determine the number of good determination methods based on all existing declarations and their current contents at that point, modulo 998244353. The terms are defined below.

Determination Method

A determination method is a way to independently choose and write either 0 or 1 into each declaration whose content is X among all current declarations, making all declaration contents either 0 or 1. The contents of declarations that are already 0 or 1 remain unchanged. Two determination methods are different if they differ in the value written to some declaration with content X. If there are 0 declarations with content X, there is exactly 1 determination method.

Good Determination Method

A determination method is called a good determination method if, after determining all declaration contents using that method, there exists at least one team division (a way to assign each person to one of the two teams) that satisfies all declarations simultaneously.

Here, a declaration (u, v, c) with determined content (c \in \{0, 1\}) is satisfied when:

  • If c = 0: person u and person v belong to the same team
  • If c = 1: person u and person v belong to different teams

Supplement (graph-theoretic rephrasing): Consider a multigraph where each person is a vertex and each declaration is an edge (no self-loops since u \neq v). After determination, each edge has a weight of 0 or 1. The necessary and sufficient condition for the existence of a team division that satisfies all declarations simultaneously is that the XOR of edge weights along every cycle in this graph is 0.

Constraints

  • 2 \leq N \leq 3000
  • 1 \leq Q \leq 3000
  • In A u v c, 1 \leq u, v \leq N and u \neq v
  • In A u v c, c is one of 0, 1, X
  • In R k, letting M be the total number of declarations at the time of that operation, 1 \leq k \leq M - 1 (it is guaranteed that both declaration k and declaration k+1 exist)
  • The total number of declarations across all operations (number of A operations) is at most Q
  • R operations do not add or remove declarations
  • N, Q, u, v, k are integers

Input

N Q
query_1
query_2
\vdots
query_Q
  • The first line contains an integer N representing the number of people and an integer Q representing the number of operations, separated by a space.
  • The following Q lines give operation query_i in one of the following formats:
  • A u v c
  • Add a declaration targeting the pair of people u and v.
  • c is one of 0, 1, X.
  • R k
  • Overwrite the content of declaration k+1 with the value obtained by adding 1 to the current content of declaration k.

Output

Output Q lines.

On the i-th line, output the number of good determination methods immediately after the i-th operation, modulo 998244353.

Sample Input 1

3 5
A 1 2 0
A 2 3 X
A 1 3 1
R 2
R 1

Sample Output 1

1
2
1
2
1

Sample Input 2

3 6
A 1 2 0
A 2 3 0
A 1 3 1
A 1 3 X
R 3
R 1

Sample Output 2

1
1
0
0
0
0

Sample Input 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

Sample Output 3

2
2
2
4
2
4
2
2
4
4
8
4
8
4
4

Sample Input 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

Sample Output 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

Sample Input 5

2 1
A 1 2 X

Sample Output 5

2