No.2293 無向辺 2-SAT
レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 56
作問者 :
t98slider
/ テスター :
hikikomori
タグ : / 解いたユーザー数 56
作問者 :
t98slider
/ テスター :
hikikomori
問題文最終更新日: 2023-07-04 22:19:18
問題文
$N$ 個の論理変数 $x = (x_{1}, x_{2}, x_{3}, \cdots, x_{N})$ があります。それぞれの論理変数は、0または1の値を割り振ることができます。
論理変数間の条件を加えることのできるスタック $S$ があります。初期段階では、スタック $S$ は空の状態で $N$ 個の論理変数には自由に値を割り当てることができます。
以下のような$Q$ 個のクエリが与えられるので順に処理してください。
1 u v：スタック $S$ に $\{(x_{u} = 1) \lor (x_{v} = 0)\} \land \{(x_{u} = 0) \lor (x_{v} = 1)\}$ という条件を加える。2 u v：スタック $S$ に $\{(x_{u} = 0) \lor (x_{v} = 0)\} \land \{(x_{u} = 1) \lor (x_{v} = 1)\}$ という条件を加える。3：スタック $S$ を空の状態にする。
クエリについての表現をやわらかくした文章 (クリックで展開します)
以下のような$Q$ 個のクエリが与えられるので順に処理してください。
1 u v：論理変数 $x_{u}$ と $x_{v}$ について同じ値が割り当てられるようにするという条件を加えます。$ (x_{u}, x_{v}) = (0, 0)$ または $ (1, 1) $2 u v：論理変数 $x_{u}$ と $x_{v}$ について異なる値が割り当てられるようにするという条件を加えます。$ (x_{u}, x_{v}) = (1, 0)$ または $ (0, 1) $3：今まで加えた条件をなかったことにします。
補足：
タイプ1のクエリに対応する真理値表は以下のようになっています。
| $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$ |
タイプ2のクエリに対応する真理値表は以下のようになっています。
| $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$ |
入力
$N\ \ Q$
${\rm Query}_{1}$
${\rm Query}_{2}$
${\rm Query}_{3}$
$\ \ \ \ \vdots$
${\rm Query}_{i}$
$\ \ \ \ \vdots$
${\rm Query}_{Q}$
- ${\rm Query}_{i}$について
タイプ1のクエリまたはタイプ2のクエリのとき${\rm type}_{i}\ u_{i}\ v_{i}$タイプ3のクエリのとき${\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$
- 入力はすべて整数
出力
$i\ (1 \leq i \leq Q)$ 行目に $i$ 個目のクエリ処理後に条件をすべて満たす論理変数の割り当て方が何通りあるかを $\bmod\ 998244353$ で出力してください。 最後に改行してください。
サンプル
サンプル1
入力
3 6 1 1 1 1 1 2 1 1 3 2 1 3 3 2 1 2
出力
8 4 2 0 8 4
サンプル1の説明を見る (クリックで展開します)
1 1 1：1つ目のクエリでは、$\{(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)$
の8通りの割り当てが可能なので8を出力します。1 1 2：2つ目のクエリでは、$\{(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)$
の4通りの割り当てが可能なので4を出力します。1 1 3：3つ目のクエリでは、$\{(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)$
の2通りの割り当てが可能なので2を出力します。2 1 3：4つ目のクエリでは、$\{(x_{1} = 0) \lor (x_{3} = 0)\} \land \{(x_{1} = 1) \lor (x_{3} = 1)\}$ という条件を加えます。
0通りの割り当てが可能なので0を出力します。3：5つ目のクエリでは、今まで加えた条件をなかったことにます。
$(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)$
の8通りの割り当てが可能なので8を出力します。2 1 2：6つ目のクエリでは、$\{(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)$
の4通りの割り当てが可能なので4を出力します。
サンプル2
入力
200000 8 1 89665 165712 2 196000 34983 2 68937 26550 1 134868 1102 3 2 47394 59946 3 1 181969 181298
出力
895248717 946746535 972495444 486247722 792253081 895248717 792253081 895248717
サンプル3
入力
10 7 1 6 3 1 3 2 2 3 8 1 9 3 2 3 10 2 8 1 2 7 8
出力
512 256 128 64 32 16 8
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。