AT_abc321_g [ABC321G] Electric Circuit

题目描述

有 $N$ 个编号为 $1$ 到 $N$ 的部件和 $M$ 根电缆，打算用它们制作电路。这些部件上共有 $M$ 个红色端子和 $M$ 个蓝色端子，第 $i$ 个红色端子在部件 $R_i$ 上，第 $i$ 个蓝色端子在部件 $B_i$ 上。每根电缆连接一个红色端子和一个蓝色端子。特别地，允许连接同一个部件上的两个端子。同时，一个端子不能连接超过一根电缆。因此，$M$ 根电缆的所有连接方式共有 $M!$ 种（注意电缆之间不区分）。

将部件视为顶点，电缆视为边，把这个电路看作一个图，记其连通分量数为 $s$。从 $M!$ 种电缆连接方式中随机选择一种时，$s$ 的期望值是多少？请将结果对 $998244353$ 取模后输出。

关于对 $998244353$ 取模的期望值
可以证明，所求期望值一定是有理数。在本题的约束下，设其化为最简分数 $\frac{P}{Q}$，则存在唯一的整数 $R$ 满足 $R\times Q\equiv P\pmod{998244353}$ 且 $0\leq R<998244353$。请输出这个 $R$。

输入格式

输入从标准输入读入，格式如下：

$N$ $M$ $R_1$ $R_2$ $\dots$ $R_M$ $B_1$ $B_2$ $\dots$ $B_M$

输出格式

输出 $s$ 的期望值对 $998244353$ 取模后的结果。

输入输出样例 #1

输入 #1

3 2
1 2
3 2

输出 #1

499122178

输入输出样例 #2

输入 #2

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

输出 #2

17

输入输出样例 #3

输入 #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

说明/提示

限制

• $1\leq N\leq 17$
• $1\leq M\leq 10^5$
• $1\leq R_i, B_i\leq N$
• 输入均为整数

样例解释 1

用 $(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}$。

样例解释 2

无论如何连接，$s=N$。

由 ChatGPT 4.1 翻译