Score : $600$ points

问题描述

你正在使用 $N$ 个编号为 $1$ 到 $N$ 的部件和 $M$ 根电缆创建一个电路。这些部件共有 $M$ 个红色接头和 $M$ 个蓝色接头，其中第 $i$ 个红色接头连接到部件 $R_i$，第 $i$ 个蓝色接头连接到部件 $B_i$。每根电缆连接一个红色接头和一个蓝色接头，特别地，允许将同一个部件上的两个接头连接起来。不允许在一个接头上连接两根或更多的电缆。因此，总共有 $M!$ 种不同的方式来连接这 $M$ 根电缆（不区分电缆之间）。

令 $s$ 表示当把这个电路看作是一个由部件作为顶点、电缆作为边的图时的连通分量数量。在随机从 $M!$ 种方式中选择一种来连接 $M$ 根电缆时，求 $s$ 的期望值对 $998244353$ 取模的结果。

寻找一个对 $998244353$ 取模后的期望值是什么意思？可以证明所求的期望值始终是一个有理数。此外，在本题的约束条件下，可以证明当该值表示为两个互质整数 $P$ 和 $Q$ 的形式 $\frac{P}{Q}$ 时，存在恰好一个整数 $R$ 满足 $R \times Q \equiv P\pmod{998244353}$ 以及 $0 \leq R < 998244353$。找出这个 $R$。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 01:41:36