102913: [Atcoder]ABC291 D - Flip Cards
Description
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
Input
题意翻译
- 有 $n$ 个卡片排成一排，编号为 $1,2,...,n$。 - 第 $i$ 个卡片的正面是 $a_i$，反面是 $b_i$。 - 现在你可以将每个卡片翻到正面或反面，使相邻两个卡片上的数字互不相同。 - 求方案数对 $998244353$ 取模。 - $1\le n\le2\times10^5$，$1\le a_i,b_i\le 10^9$Output
问题描述
将标有数字$1$到$N$的$N$张卡片排成一行。对于每一对相邻的卡片$i\ (1\leq i < N)$，卡片$i$和卡片$(i+1)$相邻。卡片$i$的正面写有$A_i$，背面写有$B_i$。起初，所有卡片正面朝上。
考虑从$N$张卡片中选择零张或多张进行翻转。在$2^N$种选择卡片翻转的方法中，找出满足以下条件的方法的数量（对$998244353$取模）：
- 当选择的卡片翻转后，每一对相邻的卡片，正面朝上的数字都不同。
约束条件
- $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$到卡片$3$，正面朝上的数字分别是$1,2$和$4$，因此满足条件。
而当选择$S=\{3\}$时，从卡片$1$到卡片$3$，正面朝上的数字分别是$1,4$和$4$，其中卡片$2$和卡片$3$上的数字相同，违反了条件。
有四个$S$满足条件：$\{\},\{1\},\{2\}$和$\{2,3\}$。
样例输入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