← 返回题目列表

AtCoder · abc321_g

G. 电路

中文机器翻译题面 查看原题

分数: 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