No.2585 How many "Who is Santa?"
Problem Statement
You are given an integer $N$.
You have decided to create test cases for the following problem "Who is Santa?" in which the input value $M$ equals $N$.
Among the inputs satisfying the constraints of "Who is Santa?", print the number of those with $M=N$, modulo $998244353$.
See the samples for details.
Who is Santa?
Problem Statement
There are $M$ people numbered from $1$ to $M$.
Exactly $1$ of the $M$ people is Santa, and all $M$ people know who it is.
Person $i$ makes a statement about person $A_i(i \neq A_i)$: that they are not Santa when $L_i = 0$, and that they are Santa when $L_i = 1$.
Santa always lies, and everyone who is not Santa always tells the truth.
The people make their statements so that Santa is uniquely determined as $1$ person.
What it means for Santa to be uniquely determined as $1$ person
Santa is said to be uniquely determined as $1$ person from the statements when there exists exactly $1$ integer $i$ satisfying all of the following conditions.
- Person $i$ says that person $A_i$ is Santa.
- Person $i$ is the only one who says that someone other than person $i$ is Santa.
- No one says that person $i$ is not Santa.
Find the number of the person who is Santa.
Input
$M$ $L_1$ $A_1$ $L_2$ $A_2$ : $L_M$ $A_M$
- All inputs are integers
- $2 \leq M$
- $L_i \in \{0, 1\}$
- $1 \leq A_i \leq M$
- $A_i \neq i$
- Santa is uniquely determined as $1$ person from the input
Output
Print the number of the person who is Santa.
Sample
Input
3 1 2 1 1 0 1Output
2
- Person $1$ says that person $2$ is Santa.
- Person $2$ says that person $1$ is Santa.
- Person $3$ says that person $1$ is not Santa.
Input
$N$
- $N$ is an integer
- $2 \leq N \leq 20231225$
Output
Among the inputs satisfying the constraints of "Who is Santa?", print the number of those with $M=N$, modulo $998244353$.
Print a newline at the end.
Sample
Sample 1
Input
3
Output
24
Among the inputs of "Who is Santa?", $24$ satisfy the constraints.
For example, the following input satisfies all the constraints and is one of the $24$ inputs.
3 1 2 1 1 0 2
The following input does not satisfy the constraint "Santa is uniquely determined as $1$ person from the input" and is not one of the $24$ inputs.
3 1 2 1 3 1 1
Sample 2
Input
4
Output
312
For example, the following input does not satisfy the constraint "Santa is uniquely determined as $1$ person from the input" and is not one of the $312$ inputs.
4 1 2 1 1 0 4 0 3
Sample 3
Input
3018570
Output
1213
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。