Flip Cards

题目描述

$N$ 张牌，编号为 $1$ 到 $N$，按一排排列。对于每个 i\ (1\leq i < N)，牌 $i$ 和牌 $(i+1)$ 是相邻的。 牌 $i$ 的正面写着 $A_i$，背面写着 $B_i$。最初，所有牌都是正面朝上。 考虑从 $N$ 张牌中选择若干张（可以为零张）进行翻面。 在 $2^N$ 种选择要翻的牌的方式中，求满足以下条件的方式数，对 $998244353$ 取模：

当所选的牌被翻面后，对于每一对相邻的牌，它们正面朝上的一面所写的整数都不相同。

输入格式

输入从标准输入按如下格式给出： $N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

输出一个整数，表示答案。

3
1 2
4 2
3 4

4

4
1 5
2 6
3 7
4 8

16

8
877914575 602436426
861648772 623690081
476190629 262703497
971407775 628894325
822804784 450968417
161735902 822804784
161735902 822804784
822804784 161735902

48

提示

$1\leq N \leq 2\times 10^5$ $1\leq A_i,B_i \leq 10^9$ 输入中的所有数值都是整数。设 $S$ 为被翻面的牌的编号集合。 例如，当选择 $S=\{2,3\}$ 时，从牌 $1$ 到牌 $3$ 它们可见面上写的整数分别是 $1,2$ 和 $4$，因此满足条件。 另一方面，当选择 $S=\{3\}$ 时，从牌 $1$ 到牌 $3$ 它们可见面上写的整数分别是 $1,4$ 和 $4$，其中牌 $2$ 和牌 $3$ 上的整数相同，违反条件。 共有四个 $S$ 满足条件：$\{\},\{1\},\{2\}$ 和 $\{2,3\}$。

标签: AtCoder|abc291D

来源

AtCoder|abc291D