問題一覧 > 通常問題

No.2293 Undirected Edge 2-SAT

レベル : / AI推定難易度 : 1250 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 58
作問者 : t98slider / テスター : hikikomori
お気に入りにしたユーザー ProblemId : 9138 / 自分の提出
問題文最終更新日: 2025-02-08 10:34:34
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 387 (Union Find Contest) (順位表) の他の問題:

Problem Statement

There are $N$ logical variables $x = (x_{1}, x_{2}, x_{3}, \cdots, x_{N})$. Each logical variable can be assigned the value 0 or 1.
There is a stack $S$ to which conditions between logical variables can be added. Initially, the stack $S$ is empty, and values can be freely assigned to the $N$ logical variables.

You are given $Q$ queries of the following forms. Process them in order.

  • 1 u v: Add the condition $\{(x_{u} = 1) \lor (x_{v} = 0)\} \land \{(x_{u} = 0) \lor (x_{v} = 1)\}$ to the stack $S$.
  • 2 u v: Add the condition $\{(x_{u} = 0) \lor (x_{v} = 0)\} \land \{(x_{u} = 1) \lor (x_{v} = 1)\}$ to the stack $S$.
  • 3: Make the stack $S$ empty.
After processing each query, output the number of ways to assign values to the logical variables that satisfy all the conditions added to the stack $S$, modulo $\bmod\ 998244353$.

A plainer description of the queries (click to expand)
You are given $Q$ queries of the following forms. Process them in order.
  • 1 u v: Add the condition that the logical variables $x_{u}$ and $x_{v}$ must be assigned the same value: $ (x_{u}, x_{v}) = (0, 0)$ or $ (1, 1) $
  • 2 u v: Add the condition that the logical variables $x_{u}$ and $x_{v}$ must be assigned different values: $ (x_{u}, x_{v}) = (1, 0)$ or $ (0, 1) $
  • 3: Discard all the conditions added so far.
After processing each query, output the number of ways to assign values to the logical variables that satisfy all the conditions, modulo $\bmod\ 998244353$.


Note:
The truth table corresponding to type 1 queries is as follows.
　$x_{u}$　　$x_{v}$　　$(x_{u} = 1) \lor (x_{v} = 0)$　　$(x_{u} = 0) \lor (x_{v} = 1)$　　$\{(x_{u} = 1) \lor (x_{v} = 0)\}\ \land\ \{(x_{u} = 0) \lor (x_{v} = 1)\}$　
　$0$　$0$　　　　　　$1$　　　　　　$1$　　　　　　　　　　　　　$1$
　$0$　$1$　　　　　　$0$　　　　　　$1$　　　　　　　　　　　　　$0$
　$1$　$0$　　　　　　$1$　　　　　　$0$　　　　　　　　　　　　　$0$
　$1$　$1$　　　　　　$1$　　　　　　$1$　　　　　　　　　　　　　$1$

The truth table corresponding to type 2 queries is as follows.
　$x_{u}$　　$x_{v}$　　$(x_{u} = 0) \lor (x_{v} = 0)$　　$(x_{u} = 1) \lor (x_{v} = 1)$　　$\{(x_{u} = 0) \lor (x_{v} = 0)\}\ \land\ \{(x_{u} = 1) \lor (x_{v} = 1)\}$　
　$0$　$0$　　　　　　$1$　　　　　　$0$　　　　　　　　　　　　　$0$
　$0$　$1$　　　　　　$1$　　　　　　$1$　　　　　　　　　　　　　$1$
　$1$　$0$　　　　　　$1$　　　　　　$1$　　　　　　　　　　　　　$1$
　$1$　$1$　　　　　　$0$　　　　　　$1$　　　　　　　　　　　　　$0$

Input

$N\ \ Q$
${\rm Query}_{1}$
${\rm Query}_{2}$
${\rm Query}_{3}$
$\ \ \ \ \vdots$
${\rm Query}_{i}$
$\ \ \ \ \vdots$
${\rm Query}_{Q}$

  • For ${\rm Query}_{i}$:
    For a type 1 query or a type 2 query 
    ${\rm type}_{i}\ u_{i}\ v_{i}$
    For a type 3 query 
    ${\rm type}_{i}$
  • $1 \leq N, Q \leq 2 \times 10^{5}$
  • $1 \leq {\rm type}_{i} \leq 3$
  • $1 \leq u_{i}, v_{i} \leq N$
  • All inputs are integers.

Output

On the $i\ (1 \leq i \leq Q)$-th line, output the number of ways to assign the logical variables so that all the conditions are satisfied after processing the $i$-th query, modulo $\bmod\ 998244353$. Print a newline at the end.

Sample

Sample 1
Input
3 6
1 1 1
1 1 2
1 1 3
2 1 3
3
2 1 2
Output
8
4
2
0
8
4

See the explanation of Sample 1 (click to expand)
  • 1 1 1: The 1st query adds the condition $\{(x_{1} = 1) \lor (x_{1} = 0)\} \land \{(x_{1} = 0) \lor (x_{1} = 1)\}$.
    $(x_{1}, x_{2}, x_{3}) = (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)$
    These 8 assignments are possible, so output 8.
  • 1 1 2: The 2nd query adds the condition $\{(x_{1} = 1) \lor (x_{2} = 0)\} \land \{(x_{1} = 0) \lor (x_{2} = 1)\}$.
    $(x_{1}, x_{2}, x_{3}) = (0, 0, 0), (0, 0, 1), (1, 1, 0), (1, 1, 1)$
    These 4 assignments are possible, so output 4.
  • 1 1 3: The 3rd query adds the condition $\{(x_{1} = 1) \lor (x_{3} = 0)\} \land \{(x_{1} = 0) \lor (x_{3} = 1)\}$.
    $(x_{1}, x_{2}, x_{3}) = (0, 0, 0), (1, 1, 1)$
    These 2 assignments are possible, so output 2.
  • 2 1 3: The 4th query adds the condition $\{(x_{1} = 0) \lor (x_{3} = 0)\} \land \{(x_{1} = 1) \lor (x_{3} = 1)\}$.
    0 assignments are possible, so output 0.
  • 3: The 5th query discards all the conditions added so far.
    $(x_{1}, x_{2}, x_{3}) = (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)$
    These 8 assignments are possible, so output 8.
  • 2 1 2: The 6th query adds the condition $\{(x_{1} = 0) \lor (x_{2} = 0)\} \land \{(x_{1} = 1) \lor (x_{2} = 1)\}$.
    $(x_{1}, x_{2}, x_{3}) = (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1)$
    These 4 assignments are possible, so output 4.

Sample 2
Input
200000 8
1 89665 165712
2 196000 34983
2 68937 26550
1 134868 1102
3
2 47394 59946
3
1 181969 181298
Output
895248717
946746535
972495444
486247722
792253081
895248717
792253081
895248717

Sample 3
Input
10 7
1 6 3
1 3 2
2 3 8
1 9 3
2 3 10
2 8 1
2 7 8
Output
512
256
128
64
32
16
8

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。