Electric Circuit

题目描述

你正在用编号为 $1$ 到 $N$ 的 $N$ 个零件和 $M$ 根电缆创建一个电路。
这些零件总共有 $M$ 个红色端子和 $M$ 个蓝色端子，第 $i$ 个红色端子连接在零件 $R_i$ 上，第 $i$ 个蓝色端子连接在零件 $B_i$ 上。
每根电缆连接一个红色端子和一个蓝色端子。
特别地，允许连接两个附着在同一零件上的端子。
你不能在一个端子上连接两根或更多电缆。
因此，总共有 $M!$ 种连接这 $M$ 根电缆的方式（电缆之间不区分）。
令 $s$ 为当把该电路视为以零件为顶点、电缆为边的图时的连通分量个数。
在从这 $M!$ 种方式中随机选择连接方式的情况下，求 $s$ 的期望值，模 $998244353$。

输入格式

输入从标准输入给出，格式如下： $N$ $M$
$R_1$ $R_2$ $\dots$ $R_M$
$B_1$ $B_2$ $\dots$ $B_M$

输出格式

输出 $s$ 的期望值，模 $998244353$。

3 2
1 2
3 2

499122178

17 5
1 1 1 1 1
1 1 1 1 1

17

8 10
2 4 7 1 7 6 1 4 8 1
5 1 5 2 5 8 4 6 1 3

608849831

提示

$1\leq N \leq 17$ $1 \leq M \leq 10^5$ $1 \leq R_i, B_i \leq N$ 所有输入值均为整数。记 $(i, j)$ 表示将第 $i$ 个红色端子和第 $j$ 个蓝色端子用一根电缆连接的操作。

对于 $(1,1), (2,2)$：将会有两个连通分量，$\lbrace 1,3 \rbrace$ 和 $\lbrace 2 \rbrace$，所以 $s=2$。
对于 $(1,2), (2,1)$：整个图构成一个连通分量，所以 $s=1$。

因此，$s$ 的期望值为 $\frac{3}{2} \equiv 499122178 \pmod {998244353}$。
$s=N$ 无论你如何连接电缆。

标签: AtCoder|abc321G

来源

AtCoder|abc321G