← 返回题目列表

AtCoder · past202109_o

O. 红蓝锦标赛

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

分数: 6 点

警告

2021 年 10 月 2 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

给你一个排列 (P_1, P_2, \ldots ,P_{2^N}) of (1,\ldots, 2^N)。 考虑进行淘汰赛 2^N ID 号码来自 1 通过 2^N。比赛由 N 回合如下。

  • 第一轮包括 2^{N-1} 游戏。的 i第一场比赛 (1 \leq i \leq 2^{N - 1}) 是玩家之间 P_{2i-1} 和玩家 P_{2i}.
  • 然后,对于每个 k = 2, \dots, N 按此顺序, k第一轮的发生如下。
    • 的 k- 第轮包括 2^{N - k} 游戏。的 i第一场比赛 (1 \leq i \leq 2^{N - k}) 是在获胜者之间 (2i - 1)-th 和 2i第 场比赛 (k-1)- 第轮。

在锦标赛开始之前,每个玩家都会被分配一种颜色,即红色或蓝色。所有玩家可能被分配相同的颜色。

在此,已知有关锦标赛结果的以下信息。

  • 在每场比赛中,如果两名玩家分配的颜色相同,则 ID 号较小的玩家获胜。
  • 在每场比赛中,如果两名玩家分配的颜色不同,则 ID 号较大的玩家获胜。
  • 对于每个 1\leq i\leq M,玩家 W_i 和玩家 L_i 在某场比赛中战斗,并且玩家 W_i 赢了。

求为满足上述所有条件的玩家分配颜色的方法数量,取模 998244353。请注意,信息可能是错误的,并且可能存在零种分配满足条件的颜色的方法。

约束

  • 1 \leq N \leq 17
  • 1 \leq M < 2^N
  • 1 \leq P_i \leq 2^N
  • 全部 P_i 是不同的。
  • 1 \leq W_i, L_i \leq 2^N
  • W_i\neq L_i
  • 所有对 (W_i,L_i) 是不同的。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
P_1 \ldots P_{2^N}
W_1 L_1
\vdots
W_M L_M

输出

打印满足条件的分配颜色的方式数,取模 998244353.


示例输入 1

1 1
2 1
1 2

示例输出 1

2

锦标赛由一场比赛组成。 从玩家的实际情况来看 1 和 2 与玩家战斗 1 赢了,我们得知他们被分配了相同的颜色。因此,可以通过两种方式为玩家分配颜色:(红,红)和(蓝,蓝)。


示例输入 2

2 2
1 2 3 4
2 3
1 2

示例输出 2

0

玩家之间的游戏 2 和 3 只能是第二轮的第一场比赛,所以玩家 2 必须在第一轮获胜。
另一方面,玩家之间的游戏 1 和 2 只能是第一轮的第一场比赛,但信息显示玩家 1 在那里获胜。
因此,我们得出结论,该信息是矛盾的,并且与之一致的颜色分配为零。