103704: [Atcoder]ABC370 E - Avoid K Partition

Problem Statement

You are given a sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$ and an integer $K$.
There are $2^{N-1}$ ways to divide $A$ into several contiguous subsequences. How many of these divisions have no subsequence whose elements sum to $K$? Find the count modulo $998244353$.

Here, "to divide $A$ into several contiguous subsequences" means the following procedure.

• Freely choose the number $k$ $(1 \leq k \leq N)$ of subsequences and an integer sequence $(i_1, i_2, \dots, i_k, i_{k+1})$ satisfying $1 = i_1 \lt i_2 \lt \dots \lt i_k \lt i_{k+1} = N+1$.
• For each $1 \leq n \leq k$, the $n$-th subsequence is formed by taking the $i_n$-th through $(i_{n+1} - 1)$-th elements of $A$, maintaining their order.

Here are some examples of divisions for $A = (1, 2, 3, 4, 5)$:

• $(1, 2, 3), (4), (5)$
• $(1, 2), (3, 4, 5)$
• $(1, 2, 3, 4, 5)$

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $-10^{15} \leq K \leq 10^{15}$
• $-10^9 \leq A_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the count modulo $998244353$.

Sample Input 1

3 3
1 2 3

Sample Output 1

2

There are two divisions that satisfy the condition in the problem statement:

• $(1), (2, 3)$
• $(1, 2, 3)$

Sample Input 2

5 0
0 0 0 0 0

Sample Output 2

0

Sample Input 3

10 5
-5 -1 -7 6 -6 -2 -5 10 2 -10

Sample Output 3

428

问题陈述

给你一个长度为$N$的序列$A = (A_1, A_2, \dots, A_N)$和一个整数$K$。
有$2^{N-1}$种方法将$A$划分为几个连续的子序列。找出其中没有子序列的元素和为$K$的划分数量。计算结果对$998244353$取模。

这里，“将$A$划分为几个连续的子序列”是指以下过程。

• 自由选择子序列的数量$k$（$1 \leq k \leq N$）和满足$1 = i_1 \lt i_2 \lt \dots \lt i_k \lt i_{k+1} = N+1$的整数序列$(i_1, i_2, \dots, i_k, i_{k+1})$。
• 对于每个$1 \leq n \leq k$，第$n$个子序列由取$A$中的第$i_n$个到第$(i_{n+1} - 1)$个元素组成，保持它们的顺序。

以下是以$A = (1, 2, 3, 4, 5)$为例的几种划分：

• $(1, 2, 3), (4), (5)$
• $(1, 2), (3, 4, 5)$
• $(1, 2, 3, 4, 5)$

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $-10^{15} \leq K \leq 10^{15}$
• $-10^9 \leq A_i \leq 10^9$
• 所有输入值都是整数。

输入

输入从标准输入以下格式给出：

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

输出

打印计算结果对$998244353$取模后的值。

样本输入 1

3 3
1 2 3

样本输出 1

2

有两种划分满足问题陈述中的条件：

• $(1), (2, 3)$
• $(1, 2, 3)$

样本输入 2

5 0
0 0 0 0 0

样本输出 2

0

样本输入 3

10 5
-5 -1 -7 6 -6 -2 -5 10 2 -10

样本输出 3

428