← 返回题目列表

AtCoder · arc198_e

E. 单调或

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

分数: 900 点

问题陈述

给你一套 S = \lbrace s_1,s_2,\dots,s_M \rbrace 之间的非负整数 0 和 2^N - 1 (含)。

您以非负整数开始 x = 0。求模数 998244353,到达的方式 x = 2^N 通过执行以下操作任意多次:

  • 选择一个整数 i 与 1 \le i \le M,并替换 x 与 (x\ \mathrm{OR}\ s_i) + 1.

在这里, \mathrm{OR} 表示按位逻辑或。

约束

  • 1 \le N \le 24
  • 1 \le M \le \min(2^N,2 \times 10^{5})
  • 0 \le s_1 < s_2 < \dots < s_M < 2^N

输入

输入由标准输入按以下格式给出:

N M
s_1\ s_2\ \dots\ s_M

输出

输出路数,取模 998244353.


示例输入 1

2 2
1 2

示例输出 1

5

让 (i, k) 表示操作选择时的转换 i 并导致 x = k。满足条件的方式有五种:

  • (1,2) \rightarrow (1,4)
  • (1,2) \rightarrow (2,3) \rightarrow (1,4)
  • (1,2) \rightarrow (2,3) \rightarrow (2,4)
  • (2,3) \rightarrow (1,4)
  • (2,3) \rightarrow (2,4)

即使值的序列 x 是相同的,不同之处在于选择 i 单独计算。


示例输入 2

5 10
3 5 8 9 11 16 17 23 27 28

示例输出 2

242816764

示例输入 3

24 32
673802 709603 941436 987977 1288854 1448514 1890649 2031791 2194398 3531579 3540682 4352378 4676427 5094869 5243789 6064976 6412917 7164733 8403938 9123034 10396333 10558625 10726446 12263566 12421464 12503511 12676340 14032527 14268967 14669703 15823827 16285412

示例输出 3

508425421