問題一覧 > 通常問題

No.2277 Honest or Dishonest ?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 125
作問者 : magstamagsta / テスター : miscalcmiscalc
5 ProblemId : 5038 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-04-20 19:33:40

問題文

$N$ 人の人がいます。それぞれの人は ”正直者” か ”嘘つき” です。

$Q$ 個の主張があります。 $i$ 個目の主張は人 $A_i$ が言ったものです。主張の内容は下記の通りです。

  • $($ $C_i=0$ のとき $)$ 人 $B_i$ は ”正直者” である。
  • $($ $C_i=1$ のとき $)$ 人 $B_i$ は ”嘘つき” である。

$N$ 人の人の ”正直者” か ”嘘つき” かの組み合わせは $2^N$ 通りあります。これらのうちどの主張とも矛盾がないものの個数を $998244353$ で割った余りを求めてください。


・主張について

”正直者” である人は ”正直者” の人のことを "正直者" であると主張し、 ”嘘つき” のことを ”嘘つき” であると主張します。

”嘘つき” である人は ”正直者” の人のことを "嘘つき" であると主張し、 ”嘘つき” のことを ”正直者” であると主張します。

入力

$N\ \ Q$
$A_1\ \ B_1\ \ C_1$
$A_2\ \ B_2\ \ C_2$
$:$
$A_Q\ \ B_Q\ \ C_Q$

  • $2 \leq N \leq 10^5$
  • $1 \leq Q \leq 10^5$
  • $1 \leq A_i,B_i \leq N$
  • $A_i \neq B_i$
  • $(A_i, B_i) \neq (A_j, B_j) \ (i \neq j)$
  • $C_i$ は $0$ か $1$
  • 入力は全て整数である

出力

求めた値を出力し、最後に改行せよ。

サンプル

サンプル1
入力
4 3
1 2 1
2 3 1
3 1 0
出力
4

例えば、人 $1,3,4$ が正直者で人 $2$ が嘘つきであるとき、どの主張とも矛盾しません。

サンプル2
入力
3 3
1 2 1
2 3 1
3 1 1
出力
0

答えが $0$ となるときもあります。

サンプル3
入力
172 12
13 29 0
48 127 1
86 25 0
171 68 1
21 67 1
29 86 0
37 23 0
37 163 1
45 48 1
163 127 0
2 13 0
68 22 1
出力
346915093

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