103216: [Atcoder]ABC321 G - Electric Circuit
Description
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
Input
Output
分数：600分
问题描述
你正在使用编号为1到N的N个零件和M根电缆构建一个电路。这些零件共有M个红色端口和M个蓝色端口，其中第i个红色端口连接到零件Ri，第i个蓝色端口连接到零件Bi。每根电缆连接一个红色端口和一个蓝色端口。特别是，可以将两个端口连接到同一个零件。你不能将两根或多根电缆连接到一个端口。因此，总共有M!种方式将M根电缆连接起来（电缆之间没有区别）。
当将此电路视为一个图形，零件作为顶点，电缆作为边时，令s为连通分量的数量。求在从M!种方式中随机选择连接M根电缆的方式时，s的期望值（模998244353）。
找到模998244353的期望值是什么意思？
可以证明所求期望值始终是一个有理数。此外，在本问题的约束条件下，可以证明当该值表示为P/Q，其中P和Q是互质的整数时，存在唯一一个满足R × Q ≡ P（模998244353）和0 ≤ R < 998244353的整数R。找到这个R。约束条件
- 1≤N≤17
- 1≤M≤105
- 1≤Ri,Bi≤N
- 所有输入值都是整数。
输入
输入将以以下格式从标准输入给出：
N M R1 R2 … RM B1 B2 … BM
输出
输出s的期望值，模998244353。
样例输入1
3 2 1 2 3 2
样例输出1
499122178
令(i, j)表示用电缆连接第i个红色端口和第j个蓝色端口的操作。
- 对于(1,1), (2,2)：将有两个连通分量，分别为{1,3}和{2}，因此s=2。
- 对于(1,2), (2,1)：整个图构成一个连通分量，因此s=1。
因此，s的期望值为3/2 ≡ 499122178（模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