102677: [AtCoder]ABC267 Ex - Odd Sum
Description
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
Input
题意翻译
- 有一个长度为 $n$ 的数列 $A$，求出选出奇数个元素和为 $m$ 的方案数 - $n\le 10^5,m\le 10^6,a_i\le 10$Output
得分：$600$分
问题描述
给你一个长度为$N$的序列$A=(A_1,A_2,\dots,A_N)$。
求出以奇数个元素从$A$中选出，使得所选元素之和等于$M$的方法数（对$998244353$取模）。
如果存在一个整数$i (1 \le i \le N)$，使得一种选择选择了$A_i$，而另一种选择没有选择$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