問題一覧 > 通常問題

No.2585 How many "Who is Santa?"

レベル : / 実行時間制限 : 1ケース 1.225秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 41
作問者 : netyo715netyo715 / テスター : 👑 p-adicp-adic
5 ProblemId : 10345 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-11-16 11:51:22

問題文

整数 $N$ が与えられます。
あなたは次の問題「Who is Santa?」の、入力の $M$ が $N$ であるようなテストケースを作ることにしました。
Who is Santa?」の制約を満たす入力の内 $M=N$ であるものの個数を $998244353$ で割ったあまりを出力してください。
詳しくはサンプルを参照してください。


Who is Santa?

問題文

$1$ から $M$ の番号が付けられた $M$ 人の人がいます。
$M$ 人の内 $1$ 人だけがサンタで、$M$ 人の人全員がそれを把握しています。
人 $i$ は人 $A_i(i \neq A_i)$ について、$L_i = 0$ のときサンタではないと、$L_i = 1$ のときサンタであると言っています。
サンタは必ず嘘を吐き、サンタでない人は必ず正しいことを言います。
人々はサンタが $1$ 人に定まるように発言しています。

サンタが $1$ 人に定まるとは

次の条件を全て満たす整数 $i$ が $1$ つだけ存在するとき、発言からサンタが $1$ 人に定まるとします。

  • 人 $i$ は人 $A_i$ がサンタであると言っている。
  • 人 $i$ 以外の人についてサンタであると言っているのは人 $i$ だけである。
  • 人 $i$ がサンタではないと言っている人が存在しない。

サンタの番号を答えてください。

入力

$M$
$L_1$ $A_1$
$L_2$ $A_2$
:
$L_M$ $A_M$

  • 入力は全て整数
  • $2 \leq M$
  • $L_i \in \{0, 1\}$
  • $1 \leq A_i \leq M$
  • $A_i \neq i$
  • 入力からサンタが $1$ 人に定まる

出力

サンタの番号を出力してください。

サンプル

入力
3
1 2
1 1
0 1
出力
2

  • 人 $1$ は人 $2$ のことをサンタだと言っています。
  • 人 $2$ は人 $1$ のことをサンタだと言っています。
  • 人 $3$ は人 $1$ のことをサンタではないと言っています。


入力

$N$

  • $N$ は整数
  • $2 \leq N \leq 20231225$

出力

Who is Santa?」の制約を満たす入力の内、 $M=N$ であるものの個数を $998244353$ で割ったあまりを出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3
出力
24

Who is Santa?」の入力の内、制約を満たすものは $24$ 個です。
例えば、次の入力は全ての制約を満たしており、$24$ 個の入力に含まれます。

3
1 2
1 1
0 2

次の入力は制約の「入力からサンタは $1$ 人に定まる」を満たさず、$24$ 個の入力に含まれません。

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

例えば、次の入力は制約の「入力からサンタは $1$ 人に定まる」を満たさず、$312$ 個の入力に含まれません。

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

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