/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
(1,\ldots, 2^N) の順列 (P_1, P_2, \ldots ,P_{2^N}) が与えられます。 選手 1 から選手 2^N までの 2^N 人がトーナメント形式で戦う事を考えます。トーナメントは N ラウンドからなり、次のように行われます。
- 第 1 ラウンドは 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}) 試合では、第 k-1 ラウンドの第 2i - 1 試合における勝者と第 2i 試合における勝者が戦う。
各選手は、トーナメントの開始前に赤か青のいずれかの色を割り当てられます。全ての選手に同じ色が割り当てられることもありえます。
いま、トーナメントの結果について以下の事が分かっています。
- 各試合において、対戦者に割り当てられた色が等しいならば、選手番号の小さい選手が勝利した。
- 各試合において、対戦者に割り当てられた色が異なるならば、選手番号の大きい選手が勝利した。
- 1\leq i\leq M について、いずれかの試合で選手 W_i と選手 L_i が戦い、選手 W_i が勝利した。
各選手に色を割り当てる方法であって、上の条件をすべてみたすものの数を 998244353 で割った余りを出力してください。ただし、情報が間違っており、条件をみたす色の割り当て方が 0 通りである可能性もあることに注意してください。
制約
- 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 試合のみからなります。 選手 1 と選手 2 が対戦して選手 1 が勝利していることから 2 人に割り当てられた色は等しかった事が分かります。よって 2 人に割り当てられた色としてあり得るのは（赤, 赤）と（青, 青）の 2 通りあります。
入力例 2
2 2 1 2 3 4 2 3 1 2
出力例 2
0
選手 2 と選手 3 が対戦するのは第 2 ラウンドの第 1 試合しかありえないので、選手 2 は第 1 ラウンドで勝利している必要があります。
一方で、選手 1 と選手 2 が対戦するのは第 1 ラウンドの第 1 試合しかありえませんが、そこでは選手 1 が勝利したことが分かっています。
よって、このようなことはあり得ず、 条件をみたす割り当て方は 0 通りであることが分かります。
Score : 6 points
Warning
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
You are given a permutation (P_1, P_2, \ldots ,P_{2^N}) of (1,\ldots, 2^N). Consider a knockout tournament with 2^N players with ID numbers from 1 through 2^N. The tournament consists of N rounds that go as follows.
- The first round consists of 2^{N-1} games. The i-th game (1 \leq i \leq 2^{N - 1}) is between Player P_{2i-1} and Player P_{2i}.
- Then, for each k = 2, \dots, N in this order, the k-th round takes place as follows.
- The k-th round consists of 2^{N - k} games. The i-th game (1 \leq i \leq 2^{N - k}) is between the winners of the (2i - 1)-th and 2i-th games in the (k-1)-th round.
Before the start of the tournament, each player is assigned a color which is red or blue. All players may be assigned the same color.
Here, the following information is known about the results of the tournament.
- In each game, if the two players were assigned the same color, the player with the smaller ID number won.
- In each game, if the two players were assigned different colors, the player with the larger ID number won.
- For each 1\leq i\leq M, Player W_i and Player L_i fought in some game, and Player W_i won.
Find the number of ways to assign colors to the players that satisfy all of the conditions above, modulo 998244353. Beware that the information may be wrong, and there may be zero ways to assign colors that satisfy the conditions.
Constraints
- 1 \leq N \leq 17
- 1 \leq M < 2^N
- 1 \leq P_i \leq 2^N
- All P_i are distinct.
- 1 \leq W_i, L_i \leq 2^N
- W_i\neq L_i
- All pairs (W_i,L_i) are distinct.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
P_1 \ldots P_{2^N}
W_1 L_1
\vdots
W_M L_M
Output
Print the number of ways to assign colors that satisfy the conditions, modulo 998244353.
Sample Input 1
1 1 2 1 1 2
Sample Output 1
2
The tournament consists of one game. From the fact that Players 1 and 2 fought and Player 1 won, we learn that they were assigned the same color. Thus, there are two ways in which the players may have been assigned colors: (red, red) and (blue, blue).
Sample Input 2
2 2 1 2 3 4 2 3 1 2
Sample Output 2
0
The game between Players 2 and 3 could only be the first game in the second round, so Player 2 must have won in the first round.
On the other hand, the game between Players 1 and 2 could only be the first game in the first round, but the information says Player 1 won there.
Therefore, we conclude that the information is contradictory, and there are zero assignments of colors that are consistent with it.