34160번 - 순열과 순열 (Hard)

문제

이 문제는 순열과 순열과 $N$의 제한만 다릅니다.

길이 $N$의 순열 $A = \left(A_1, ,円 A_2 , ,円 \cdots, ,円 A_N\right)$이 주어진다. 이때, 다음을 만족하는 일대일 대응 $f$의 개수를 구하라.

• $f : \left\{1, ,円 2, ,円 \cdots, ,円 N \right\} \rightarrow \left\{1, ,円 2, ,円 \cdots, ,円 N \right\}$. 즉, $f$는 정의역과 공역(치역)으로 집합 $\left\{1, ,円 2, ,円 \cdots, ,円 N \right\}$을 가진다.
• 1ドル \leq i \leq N$을 만족하는 모든 정수 $i$에 대해, $f(i) \neq i$이고 $f(i) \neq A_i$이다.

이때, 답이 매우 커질 수 있으므로 998ドル ,円 244 ,円 353$으로 나눈 나머지를 출력하라. 998ドル ,円 244 ,円 353$은 소수이다.

순열 및 일대일 대응의 자세한 정의는 노트를 참고하라.

입력

첫 번째 줄에 순열의 크기를 나타내는 정수 $N$이 주어진다. (2ドル \leq N \leq 200 ,円 000$)

두 번째 줄에 순열 $A$의 원소 $A_1, ,円 A_2, ,円 \cdots, ,円 A_N$이 공백으로 구분되어 주어진다. (1ドル \leq A_i \leq N,ドル $i \neq j$이면 $A_i \neq A_j$)

출력

조건을 만족하는 일대일 대응 $f$의 개수를 998ドル ,円 244 ,円 353$으로 나눈 나머지를 출력하라.

제한

노트

길이가 $N$인 순열이란 순열의 원소로 1ドル$부터 $N$까지의 정수가 모두 빠짐없이 단 한 번씩 나오는 수열을 의미한다. 즉, 순열 $A = \left(A_1, ,円 A_2 , ,円 \cdots, ,円 A_N\right)$는 아래 조건을 만족한다.

• $A_i$는 1ドル$ 이상 $N$ 이하의 정수
• $i \neq j$이면 $A_i \neq A_j$

정의역이 $D,ドル 공역이 $C$인 함수 $f : D \rightarrow C$는 집합 $D$의 각 원소에 대해 집합 $C$의 원소를 하나씩 대응시키는 규칙이다. 이때 모든 대응값은 $C$에 속하며, 함수는 $D$의 모든 원소에 대해 정의되어야 한다. 즉, 모든 $x \in D$에 대해 유일한 $f(x) \in C$가 존재하는 대응 규칙을 의미한다. 함수 $f: D \rightarrow C$의 치역은 정의역 $D$의 원소들이 $f$에 의해 실제로 대응되는 공역 $C$의 원소들의 집합이다. 즉, $f$의 치역은 $\{ f(x) \mid x \in D \} \subseteq C$을 의미한다.

함수 $f: D \rightarrow C$가 일대일 함수(단사 함수)가 되기 위해서는, 임의의 $x_1, ,円 x_2 \in D$에 대하여

$$f(x_1) = f(x_2) \implies x_1 = x_2$$

가 성립해야한다. 즉, 서로 다른 원소는 항상 서로 다른 함수값에 대응되는 함수를 의미한다.

함수 $f: D \rightarrow C$가 일대일 대응(전단사 함수)가 되기 위해서는, 함수 $f$가 일대일 함수이며 공역과 치역이 같아야 한다. 즉,

$$\forall y \in C, \exists! x \in D ,円 \text{s.t.} f(x) = y$$

이면 $f$를 일대일 대응이라고 한다.