← 返回题目列表

AtCoder · pakencamp_2022_day3_f

F. 循环和异或

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

配点 : 100 点

問題文

0 以上 2^M 的整数组成 N 序列 A=(A_0,A_1,\ldots,A_{N-1}) 的数量。 除以 998244353 求余数。

  • 所有整数 i\ (0 \le i \le N-1) , A_i \oplus A_{(i+1) \bmod N} \neq T_i 和 A_i \oplus A_{(i+1) \bmod N} \neq U_i 成立

但是 \oplus 以位为单位 \mathrm{XOR} 代表一个操作。

位单位 \mathrm{XOR} 什么是操作?

非負整数 A,B 按位 \mathrm{XOR} 演算、A\oplus B 定义如下。

  • A\oplus B 以二进制表示法 2^k\ (k\geq 0) 中的位数为A,B 以二进制表示法 2^k 数字中只有一位是 1 如果 交换 1,否则 0 。

例如, 当3\oplus 5 = 6 (二进制表示法: 011\oplus 101 = 110)。

制約

  • 2 \le N \le 2\times 10^5
  • 1 \le M \le 30
  • 0 \le T_i < U_i < 2^M
  • 所有输入均为整数

入力

输入将以以下形式通过标准输入给出。

N M
T_0 U_0
T_1 U_1
\vdots
T_{N-1} U_{N-1}

出力

打印答案。


入力例 1

3 2
0 1
1 2
2 3

出力例 1

8

A 是可能的 (0,2,1),(0,3,0),(1,3,0),(1,2,1),(2,0,3),(2,1,2),(3,1,2),(3,0,3) 的 8 没错。


入力例 2

3 1
0 1
0 1
0 1

出力例 2

0

入力例 3

5 10
31 415
92 653
58 979
32 384
62 643

出力例 3

552613140