/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
1 から N までの番号がついた N 枚のカードが一列に並んでいて、各 i\ (1\leq i < N) に対してカード i とカード i+1 が隣り合っています。 カード i の表には A_i が、裏には B_i が書かれており、最初全てのカードは表を向いています。
今から、N 枚のカードのうち好きな枚数 (0 枚でも良い) を選んで裏返すことを考えます。 裏返すカードの選び方は 2^N 通りありますが、そのうち以下の条件を満たすものの数を 998244353 で割った余りを求めてください。
- 選んだカードを裏返した後、どの隣り合う 2 枚のカードについても、向いている面に書かれた数が相異なる。
制約
- 1\leq N \leq 2\times 10^5
- 1\leq A_i,B_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
答えを整数として出力せよ。
入力例 1
3 1 2 4 2 3 4
出力例 1
4
裏返すカードの番号の集合を S とします。
例えば S=\{2,3\} を選ぶと、向いている面に書かれた数はカード 1 から順に 1,2,4 となるため条件を満たします。
一方 S=\{3\} を選ぶと、向いている面に書かれた数はカード 1 から順に 1,4,4 となり、カード 2 とカード 3 の数が一致するため条件を満たしません。
条件を満たす S は \{\},\{1\},\{2\},\{2,3\} の 4 通りです。
入力例 2
4 1 5 2 6 3 7 4 8
出力例 2
16
入力例 3
8 877914575 602436426 861648772 623690081 476190629 262703497 971407775 628894325 822804784 450968417 161735902 822804784 161735902 822804784 822804784 161735902
出力例 3
48
Score : 400 points
Problem Statement
N cards, numbered 1 through N, are arranged in a line. For each i\ (1\leq i < N), card i and card (i+1) are adjacent to each other. Card i has A_i written on its front, and B_i written on its back. Initially, all cards are face up.
Consider flipping zero or more cards chosen from the N cards. Among the 2^N ways to choose the cards to flip, find the number, modulo 998244353, of such ways that:
- when the chosen cards are flipped, for every pair of adjacent cards, the integers written on their face-up sides are different.
Constraints
- 1\leq N \leq 2\times 10^5
- 1\leq A_i,B_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print the answer as an integer.
Sample Input 1
3 1 2 4 2 3 4
Sample Output 1
4
Let S be the set of card numbers to flip.
For example, when S=\{2,3\} is chosen, the integers written on their visible sides are 1,2, and 4, from card 1 to card 3, so it satisfies the condition.
On the other hand, when S=\{3\} is chosen, the integers written on their visible sides are 1,4, and 4, from card 1 to card 3, where the integers on card 2 and card 3 are the same, violating the condition.
Four S satisfy the conditions: \{\},\{1\},\{2\}, and \{2,3\}.
Sample Input 2
4 1 5 2 6 3 7 4 8
Sample Output 2
16
Sample Input 3
8 877914575 602436426 861648772 623690081 476190629 262703497 971407775 628894325 822804784 450968417 161735902 822804784 161735902 822804784 822804784 161735902
Sample Output 3
48