该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Avoid K Partition

题目描述

给定一个长度为 $N$ 的序列 $A = (A_1, A_2, \dots, A_N)$ 和一个整数 $K$。
将 $A$ 划分为若干个连续子序列的方式共有 $2^{N-1}$ 种。其中，有多少种划分使得不存在任一子序列的元素之和等于 $K$？请计算该数量对 $998244353$ 取模后的结果。 这里，“将 $A$ 划分为若干个连续子序列”指以下过程。

任意选择子序列的个数 $k$ $(1 \leq k \leq N)$ 以及一个整数序列 $(i_1, i_2, \dots, i_k, i_{k+1})$ 满足 $1 = i_1 \lt i_2 \lt \dots \lt i_k \lt i_{k+1} = N+1$。 对于每个 $1 \leq n \leq k$，第 $n$ 个子序列由第 $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

5 0
0 0 0 0 0

0

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

428

提示

$1 \leq N \leq 2 \times 10^5$ $-10^{15} \leq K \leq 10^{15}$ $-10^9 \leq A_i \leq 10^9$ 所有输入值均为整数。满足题目条件的划分有两种：

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

标签: AtCoder|abc370E

来源

AtCoder|abc370E