実行時間制限: 2 sec / メモリ制限: 1024 MB
Score : 600 points
Problem Statement
There are 2N people numbered 1 through 2N. The height of Person i is h_i.
How many ways are there to make N pairs of people such that the following conditions are satisfied? Compute the answer modulo 998,244,353.
- Each person is contained in exactly one pair.
- For each pair, the heights of the two people in the pair are different.
Two ways are considered different if for some p and q, Person p and Person q are paired in one way and not in the other.
Constraints
- 1 \leq N \leq 50,000
- 1 \leq h_i \leq 100,000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N h_1 : h_{2N}
Output
Print the answer.
Sample Input 1
2 1 1 2 3
Sample Output 1
2
There are two ways:
- Form the pair (Person 1, Person 3) and the pair (Person 2, Person 4).
- Form the pair (Person 1, Person 4) and the pair (Person 2, Person 3).
Sample Input 2
5 30 10 20 40 20 10 10 30 50 60
Sample Output 2
516
配点 : 600 点
問題文
2N 人の人 (1 番から 2N 番まで) がいます。 人 i の身長は h_i です。
以下の条件を満たすように、N 個の人のペアを作る方法は何通りありますか? 答えを modulo 998,244,353 で求めてください。
- どの人もちょうど一つのペアに含まれる。
- どのペアも、そのペアに属する二人の人の身長が異なる。
ある p と q に対し、人 p と人 q がペアになったかどうかが異なる場合、異なる方法であるとみなします。
制約
- 1 \leq N \leq 50,000
- 1 \leq h_i \leq 100,000
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N h_1 : h_{2N}
出力
答えを出力せよ。
入力例 1
2 1 1 2 3
出力例 1
2
二通りあります:
- ペア (人 1, 人 3) とペア (人 2, 人 4) を作る。
- ペア (人 1, 人 4) とペア (人 2, 人 3) を作る。
入力例 2
5 30 10 20 40 20 10 10 30 50 60
出力例 2
516