/ 
Time Limit: 7 sec / Memory Limit: 1024 MiB
配点 : 900 点
問題文
0 以上 2^N 未満の非負整数からなる集合 S = \lbrace s_1,s_2,\dots,s_M \rbrace が与えられます。
あなたは非負整数 x = 0 を持っています。以下の操作を好きな回数行い、x = 2^N とする方法の個数を 998244353 で割った余りを求めてください。
- 1 \le i \le M を満たす整数 i を選び、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 を選んで操作を行い、x = k となった場合、その遷移を (i, k) と表記します。条件を満たす方法は以下の 5 通りです。
- (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
Score : 900 points
Problem Statement
You are given a set S = \lbrace s_1,s_2,\dots,s_M \rbrace of non-negative integers between 0 and 2^N - 1 (inclusive).
You start with a non-negative integer x = 0. Find the number, modulo 998244353, of ways to reach x = 2^N by performing the following operation any number of times:
- Choose an integer i with 1 \le i \le M, and replace x with (x\ \mathrm{OR}\ s_i) + 1.
Here, \mathrm{OR} denotes the bitwise logical OR.
Constraints
- 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
Input
The input is given from Standard Input in the following format:
N M s_1\ s_2\ \dots\ s_M
Output
Output the number of ways, modulo 998244353.
Sample Input 1
2 2 1 2
Sample Output 1
5
Let (i, k) denote the transition when an operation chooses i and results in x = k. There are five ways that satisfy the conditions:
- (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)
Even if the sequence of values of x is identical, ways that differ in the choices of i are counted separately.
Sample Input 2
5 10 3 5 8 9 11 16 17 23 27 28
Sample Output 2
242816764
Sample Input 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
Sample Output 3
508425421