分数: 600 点
问题陈述
您正在使用以下命令创建电路 N 零件编号 1 to N 和 M 电缆。 这些部分总共有 M 红色端子和 M 蓝色端子,与 i连接到零件的第一个红色端子 R_i 和 i连接到零件的第一个蓝色端子 B_i。 每根电缆连接一个红色端子和一个蓝色端子。 特别地,允许连接附接到同一部件的两个端子。 不能将两根或多根电缆连接到一个端子。 因此,有 M! 总共连接方式 M 电缆(这些电缆彼此不区分)。
让 s 是将该电路视为以部件为顶点、电缆为边的图形时连接的组件的数量。 求期望值,取模 998244353,属于 s 当随机选择连接方式时 M 电缆出 M! 方式。
求期望值模是什么意思 998244353?
可以证明,求的期望值始终是有理数。 并且,在该问题的约束下,可以证明,当该值表示为 \frac{P}{Q} 使用两个互质整数 P 和 Q,恰好有一个整数 R 满足 R \times Q \equiv P\pmod{998244353} 和 0 \leq R \lt 998244353。 找到这个 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,模数 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,所以 s=2.
- 对于 (1,2), (2,1):整个图构成一个连通分量,所以 s=1.
因此,预期值 s is \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