避免和为 K 的分割

题目描述

给你长度为 $N$ 的序列 $A = (A_1, A_2, \dots, A_N)$ 和一个整数 $K$。

把 $A$ 分成若干个连续子序列共有 $2^{N-1}$ 种方法。其中,有多少种分法使得没有任何一个子序列的元素和为 $K$?答案对 $998244353$ 取模。

这里,"把 $A$ 分成若干个连续子序列"指以下过程:

自由选择子序列个数 $k$ $(1 \le k \le 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 \le n \le 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)$

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出满足问题条件的划分数对 $998244353$ 取模的结果。

样例

3 3
1 2 3

2

满足问题条件的划分有以下两种:

$(1), (2, 3)$

$(1, 2, 3)$

5 0
0 0 0 0 0

0

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

428

数据范围

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