/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 から N までの番号が付けられた N 個の部品と M 本のケーブルを使って電気回路を作ろうとしています。 これらの部品には赤い端子と青い端子がそれぞれ合計で M 個ずつ存在し、i 個目の赤い端子は部品 R_i に、i 個目の青い端子は部品 B_i についています。 各ケーブルは赤い端子 1 つと青い端子 1 つを繋ぎます。 特に、同じ部品についた 2 つの端子を繋ぐことも許されます。 また、1 つの端子に対して 2 本以上のケーブルを繋げることはできません。 したがって、M 本のケーブルの繋ぎ方は全部で M! 通りあります（ケーブル同士は区別しないことに注意してください）。
部品を頂点、ケーブルを辺としたグラフとしてこの回路を見たときの連結成分数を s とします。 M 本のケーブルの繋ぎ方を M! 通りからランダムに選ぶときの s の期待値を \text{mod } 998244353 で求めてください。
期待値を \text{mod } 998244353 で求めるとは
求める期待値は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。 この R を求めてください。制約
- 1\leq N \leq 17
- 1 \leq M \leq 10^5
- 1 \leq R_i, B_i \leq N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M R_1 R_2 \dots R_M B_1 B_2 \dots B_M
出力
s の期待値を \text{mod } 998244353 で出力せよ。
入力例 1
3 2 1 2 3 2
出力例 1
499122178
i 個目の赤い端子と j 個目の青い端子をケーブルで繋ぐことを (i, j) と表記します。
- (1,1), (2,2) の場合：\lbrace 1,3 \rbrace と \lbrace 2 \rbrace という 2 つの連結成分ができるので、s=2 です。
- (1,2), (2,1) の場合：全体が 1 つの連結成分になるので、s=1 です。
よって、s の期待値は \frac{3}{2} \equiv 499122178 \pmod {998244353} です。
入力例 2
17 5 1 1 1 1 1 1 1 1 1 1
出力例 2
17
どのように繋いでも s=N になります。
入力例 3
8 10 2 4 7 1 7 6 1 4 8 1 5 1 5 2 5 8 4 6 1 3
出力例 3
608849831
Score : 600 points
Problem Statement
You are creating an electrical circuit using N parts numbered 1 to N and M cables. These parts have a total of M red terminals and M blue terminals, with the i-th red terminal attached to part R_i and the i-th blue terminal attached to part B_i. Each cable connects one red terminal and one blue terminal. In particular, it is allowed to connect two terminals attached to the same part. You cannot connect two or more cables to a terminal. Therefore, there are M! ways in total to connect the M cables (the cables are not distinguished from each other).
Let s be the number of connected components when seeing this circuit as a graph with parts as vertices and cables as edges. Find the expected value, modulo 998244353, of s when randomly choosing the way to connect the M cables out of the M! ways.
What does it mean to find an expected value modulo 998244353?
It can be proved that the sought expected value is always a rational number. Also, under the constraints of this problem, it can be proved that when this value is expressed as \frac{P}{Q} using two coprime integers P and Q, there is exactly one integer R that satisfies R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find this R.Constraints
- 1\leq N \leq 17
- 1 \leq M \leq 10^5
- 1 \leq R_i, B_i \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M R_1 R_2 \dots R_M B_1 B_2 \dots B_M
Output
Print the expected value of s, modulo 998244353.
Sample Input 1
3 2 1 2 3 2
Sample Output 1
499122178
Let (i, j) denote the action of connecting the i-th red terminal and the j-th blue terminal with a cable.
- For (1,1), (2,2): There will be two connected components, \lbrace 1,3 \rbrace and \lbrace 2 \rbrace, so s=2.
- For (1,2), (2,1): The whole graph constitutes one connected component, so s=1.
Thus, the expected value of s is \frac{3}{2} \equiv 499122178 \pmod {998244353}.
Sample Input 2
17 5 1 1 1 1 1 1 1 1 1 1
Sample Output 2
17
s=N no matter how you connect the cables.
Sample Input 3
8 10 2 4 7 1 7 6 1 4 8 1 5 1 5 2 5 8 4 6 1 3
Sample Output 3
608849831