/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 700 点
問題文
0 と 1 からなる長さ N の数列 B=(B_1,B_2,\ldots,B_N) があります。 はじめ、B_1=1 であり、それ以外の要素は 0 です。
M 個のスイッチがあり、スイッチ i (1 \le i \le M) には整数 A_i が書かれています。 スイッチ i を押すと、操作を行う直前の状態を用いて、1 \le j \le N を満たすすべての整数 j について B_j を同時に次のように変更します。
\[ B_j \leftarrow \begin{cases} B_j \oplus B_{j-A_i} & (A_i \lt j),\\ B_j & (j \le A_i) \end{cases} \]
各スイッチは 0 回または 1 回押すことができ、スイッチを押す順番は自由です。
最終的な列 B としてあり得るものの個数を 998244353 で割った余りを求めてください。
ビット単位 \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)。 一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、 これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。
制約
- 2 \le N \le 2 \times 10^5
- 1 \le M \le 2 \times 10^5
- 1 \le A_i \lt N (1 \le i \le M)
- 入力される数値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \ldots A_M
出力
最終的な列 B としてあり得るものの個数を 998244353 で割った余りを出力せよ。
入力例 1
4 2 2 3
出力例 1
4
最終的な列としてあり得るものは、次の 4 個です。
- (1,0,0,0)
- (1,0,1,0)
- (1,0,0,1)
- (1,0,1,1)
入力例 2
2 1 1
出力例 2
2
最終的な列としてあり得るものは、(1,0) と (1,1) の 2 個です。
入力例 3
96 30 56 6 46 18 9 38 20 25 18 44 46 71 44 65 42 20 38 25 9 95 18 65 71 9 95 65 9 42 65 6
出力例 3
384912
Score : 700 points
Problem Statement
There is a length-N sequence B=(B_1,B_2,\ldots,B_N) consisting of 0 and 1. Initially, B_1=1, and all other elements are 0.
There are M switches, and the integer A_i is written on switch i (1 \le i \le M). When switch i is pressed, using the state immediately before the operation, B_j is simultaneously changed as follows for every integer j satisfying 1 \le j \le N:
\[ B_j \leftarrow \begin{cases} B_j \oplus B_{j-A_i} & (A_i \lt j),\\ B_j & (j \le A_i) \end{cases} \]
Each switch can be pressed zero times or once, and the switches may be pressed in any order.
Find the number, modulo 998244353, of possible final sequences B.
What is the bitwise \mathrm{XOR} operation?
The bitwise \mathrm{XOR} of non-negative integers A and B, denoted A \oplus B, is defined as follows:
- The digit in the 2^k's place (k \geq 0) of A \oplus B, written in binary, is 1 if exactly one of the digits in the 2^k's place of A and B, written in binary, is 1, and 0 otherwise.
For example, 3 \oplus 5 = 6 (in binary: 011 \oplus 101 = 110). In general, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k), and it can be proved that this does not depend on the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 2 \le N \le 2 \times 10^5
- 1 \le M \le 2 \times 10^5
- 1 \le A_i \lt N (1 \le i \le M)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_M
Output
Output the number, modulo 998244353, of possible final sequences B.
Sample Input 1
4 2 2 3
Sample Output 1
4
There are four possible final sequences:
- (1,0,0,0)
- (1,0,1,0)
- (1,0,0,1)
- (1,0,1,1)
Sample Input 2
2 1 1
Sample Output 2
2
There are two possible final sequences: (1,0) and (1,1).
Sample Input 3
96 30 56 6 46 18 9 38 20 25 18 44 46 71 44 65 42 20 38 25 9 95 18 65 71 9 95 65 9 42 65 6
Sample Output 3
384912