/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 575 点
問題文
1 から N までの番号がついた N 個のボールが入った箱があります。各ボールには整数で表される色がついており、ボール i は色 C_i で塗られています。
高橋君は操作を N 回行いました。k 回目 (1\le k\le N) の操作は以下の通りです：
- 箱の中からボールを一様ランダムに一つ取り出して捨てる。取り出したボールが色 G_k であれば、1 点を得る。
N 回の操作で得た合計得点が 0 点となる確率を \text{mod}\ 998244353 で求めてください。
確率 \text{mod}\ 998244353 の定義
求める確率は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、求める有理数を既約分数 \frac{P}{Q} で表した時、Q {{}\not\equiv{}} 0 \pmod{998244353} となることが証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。
制約
- 1\le N\le 2\times 10^5
- 1\le C_i,G_k\le N
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N C_1 C_2 \ldots C_N G_1 G_2 \ldots G_N
出力
求めた確率を \text{mod}\ 998244353 で出力せよ。
入力例 1
3 1 2 3 1 1 2
出力例 1
332748118
例えば操作は以下のように進行します：
- 1 回目：箱の中から色 2 のボールが取り出される。
- 2 回目：箱の中から色 1 のボールが取り出される。1 点を獲得する。
- 3 回目：箱の中から色 3 のボールが取り出される。
この場合の合計得点は 1 点です。
高橋君の合計得点が 0 点となる確率は \displaystyle \frac13 です。
入力例 2
3 1 1 3 3 3 3
出力例 2
0
高橋君の合計得点は必ず 1 点となります。
入力例 3
6 1 2 3 3 4 5 3 5 3 5 5 4
出力例 3
316110712
Score : 575 points
Problem Statement
There is a box containing N balls numbered 1 through N. Each ball is painted with a color represented as an integer, and ball i is painted with color C_i.
Takahashi performed N operations. The k-th operation (1\le k\le N) is as follows:
- Draw one ball uniformly at random from the box and discard it. If the drawn ball has color G_k, gain 1 point.
Find the probability, modulo 998244353, that the total score over N operations is 0 points.
Definition of probability modulo 998244353
It can be proved that the sought probability is always a rational number. Furthermore, under the constraints of this problem, when the rational number is expressed as an irreducible fraction \frac{P}{Q}, it can be proved that Q {{}\not\equiv{}} 0 \pmod{998244353}. Thus, there exists a unique integer R satisfying R \times Q \equiv P \pmod{998244353} and 0 \leq R \lt 998244353. Find this R.
Constraints
- 1\le N\le 2\times 10^5
- 1\le C_i,G_k\le N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N C_1 C_2 \ldots C_N G_1 G_2 \ldots G_N
Output
Output the sought probability modulo 998244353.
Sample Input 1
3 1 2 3 1 1 2
Sample Output 1
332748118
For example, the operations may proceed as follows:
- First operation: A ball with color 2 is drawn from the box.
- Second operation: A ball with color 1 is drawn from the box. Gain 1 point.
- Third operation: A ball with color 3 is drawn from the box.
In this case, the total score is 1 point.
The probability that Takahashi's total score is 0 is \displaystyle \frac13.
Sample Input 2
3 1 1 3 3 3 3
Sample Output 2
0
Takahashi's total score is always 1 point.
Sample Input 3
6 1 2 3 3 4 5 3 5 3 5 5 4
Sample Output 3
316110712