← 返回题目列表

Codeforces · 1193/A

A. 游乐园

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

您已受聘监督一个新游乐园的项目。该公园将有一个特殊的噱头:定向滑梯,可以以一种有趣的方式将顾客从一个景点快速带到另一个景点。

公园所有者已向您提供当前项目:计划中的景点列表以及应在它们之间建造的滑梯列表。然而,作为一名商人,他随心所欲地设想了不可能的事情:除此之外,他投影了一个从闹鬼城堡到过山车的滑梯,另一个从过山车到降落塔的滑梯,第三个从降落塔到闹鬼城堡的滑梯。由于滑梯只能下坡,因此很明显这是一个问题。在建造公园时,你不能忽视物理定律,因此你必须要求对项目进行更改。也许他会接受在降落塔和闹鬼城堡之间反转滑梯?

正式:

- 该项目是景点列表和定向幻灯片列表。每张幻灯片从一个景点开始,到另一个景点结束。
- 通过反转某些幻灯片(可能没有或全部)的方向从项目中获得提案。
- 如果有一种方法可以为每个景点分配标高,使每个滑梯都走下坡路,那么该提案就是合法的。
- 提案的成本是方向相反的幻灯片的数量。

对于给定项目,查找并报告所有法律提案的成本总和。由于这个数字可能很大,因此输出它对 $$$998,244,353$$$ 取模。

输入

第一行包含两个空格分隔的整数 $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 18$$$, $$$0 \leq m \leq n(n-1)/2$$$) – 分别是景点数量和幻灯片数量。景点编号为 $$$1$$$ 到 $$$n$$$。

然后是 $$$m$$$ 行。这些行的第 $$$i$$$ 包含两个空格分隔的整数 $$$a_i$$$、$$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$) 表示从 $$$a_i$$$ 到 $$$b_i$$$ 的幻灯片。

您可以假设:

- 没有自环。 (对于每个$$$i$$$:$$$a_i \neq b_i$$$。)
- 幻灯片不会出现两次。 (对于所有 $$$i \neq j$$$:$$$a_i \neq a_j$$$ 或 $$$b_i \neq b_j$$$。)
- 没有一对景点在两个方向上都是相连的。 (无序对 $$$\{a_i, b_i\}$$$ 是不同的。)

输出

输出一行单个整数,即所有法律提案的成本总和以 $$$998,244,353$$$ 为模。

示例

输入 #1

2 1
1 2

输出 #1

1

输入 #2

3 3
1 2
2 3
1 3

输出 #2

9

注意

评分:
子任务 1(7 分):$$$n \leq 3$$$

子任务 2(12 分):$$$n \leq 6$$$

子任务 3(23 分):$$$n \leq 10$$$

子任务 4(21 分):$$$n \leq 15$$$

子任务5(37分):无额外限制

在第一个示例中,有两个提案:

- 滑动方向不翻转。该提案的成本为 $$$0$$$。
- 滑动方向翻转。该提案的成本为 $$$1$$$。

在第二个示例中,有八个提案,其滑动方向如下:

- $$$1 \rightarrow 2$$$、$$$2 \rightarrow 3$$$、$$$1 \rightarrow 3$$$ (成本 $$$0$$$)
- $$$1 \rightarrow 2$$$、$$$2 \rightarrow 3$$$、$$$3 \rightarrow 1$$$ (成本 $$$1$$$)
- $$$1 \rightarrow 2$$$、$$$3 \rightarrow 2$$$、$$$1 \rightarrow 3$$$ (成本 $$$1$$$)
- $$$1 \rightarrow 2$$$、$$$3 \rightarrow 2$$$、$$$3 \rightarrow 1$$$ (成本 $$$2$$$)
- $$$2 \rightarrow 1$$$、$$$2 \rightarrow 3$$$、$$$1 \rightarrow 3$$$ (成本 $$$1$$$)
- $$$2 \rightarrow 1$$$、$$$2 \rightarrow 3$$$、$$$3 \rightarrow 1$$$ (成本 $$$2$$$)
- $$$2 \rightarrow 1$$$、$$$3 \rightarrow 2$$$、$$$1 \rightarrow 3$$$ (成本 $$$2$$$)
- $$$2 \rightarrow 1$$$、$$$3 \rightarrow 2$$$、$$$3 \rightarrow 1$$$ (成本 $$$3$$$)

第二个提案不合法,因为有一个幻灯片序列 $$$1 \rightarrow 2 \rightarrow 3 \rightarrow 1$$$。这意味着吸引力$$$1$$$必须严格高于ifself,这显然是不可能的。同样,第七个提案也不合法。因此答案是 $$$0 + 1 + 2 + 1 + 2 + 3 = 9$$$。