/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
A から要素を奇数個選ぶ方法のうち、選んだ要素の総和が M になるものの個数を 998244353 で割ったあまりを求めてください。
ただし、2 つの選び方が異なるとは、ある整数 i (1 \le i \le N) が存在して、一方の選び方では A_i を選び、もう一方では選んでいないことを言います。
制約
- 1 \le N \le 10^5
- 1 \le M \le 10^6
- 1 \le A_i \le 10
- 入力は全て整数。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
5 6 1 2 3 3 6
出力例 1
3
条件を満たす選び方は以下の 3 通りです。
- A_1,A_2,A_3 を選ぶ。
- A_1,A_2,A_4 を選ぶ。
- A_5 を選ぶ。
A_3,A_4 を選んだ場合、総和は 6 ですが選んだ要素の個数が奇数個でないため条件を満たしません。
入力例 2
10 23 1 2 3 4 5 6 7 8 9 10
出力例 2
18
Score : 600 points
Problem Statement
You are given a sequence A=(A_1,A_2,\dots,A_N) of length N.
Find the number, modulo 998244353, of ways to choose an odd number of elements from A so that the sum of the chosen elements equals M.
Two choices are said to be different if there exists an integer i (1 \le i \le N) such that one chooses A_i but the other does not.
Constraints
- 1 \le N \le 10^5
- 1 \le M \le 10^6
- 1 \le A_i \le 10
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
5 6 1 2 3 3 6
Sample Output 1
3
The following 3 choices satisfy the condition:
- Choosing A_1, A_2, and A_3.
- Choosing A_1, A_2, and A_4.
- Choosing A_5.
Choosing A_3 and A_4 does not satisfy the condition because, although the sum is 6, the number of chosen elements is not odd.
Sample Input 2
10 23 1 2 3 4 5 6 7 8 9 10
Sample Output 2
18