题目描述
長さ N の整数列 A=(A1,A2,…,AN) が与えられます。
A から要素を奇数個選ぶ方法のうち、選んだ要素の総和が M になるものの個数を 998244353 で割ったあまりを求めてください。
ただし、2 つの選び方が異なるとは、ある整数 i (1 ≤ i ≤ N) が存在して、一方の選び方では Ai を選び、もう一方では選んでいないことを言います。
输入格式
入力は以下の形式で標準入力から与えられる。
N M A1 A2 … AN
输出格式
答えを出力せよ。
题目大意
-
有一个长度为 n 的数列 A,求出选出奇数个元素和为 m 的方案数
-
n≤105,m≤106,ai≤10
5 6
1 2 3 3 6
3
10 23
1 2 3 4 5 6 7 8 9 10
18
提示
制約
- 1 ≤ N ≤ 105
- 1 ≤ M ≤ 106
- 1 ≤ Ai ≤ 10
- 入力は全て整数。
Sample Explanation 1
条件を満たす選び方は以下の 3 通りです。 - A1,A2,A3 を選ぶ。 - A1,A2,A4 を選ぶ。 - A5 を選ぶ。 A3,A4 を選んだ場合、総和は 6 ですが選んだ要素の個数が奇数個でないため条件を満たしません。