Score : $600$ points

问题描述

给定一个长度为 $N$ 的序列 $A=(A_1,A_2,\dots,A_N)$。

要求计算从 $A$ 中选择奇数个元素，使得所选元素之和等于 $M$ 的方法数量，结果对 $998244353$ 取模。

如果存在一个整数 $i (1 \le i \le N)$，使得在一个选择中选取了 $A_i$，而在另一个选择中未选取，则认为这两种选择是不同的。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 11:17:29