AT_abc370_e [ABC370E] Avoid K Partition

题目描述

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

存在 $2^{N-1}$ 种方法将 $A$ 分成若干个连续子区间。有多少划分方法满足没有任何一个划分出的子区间元素和为 $K$？请输出这个值模 $998244353$ 的结果。

这里，“将 $A$ 分成若干个连续子区间”的含义如下：

• 随意选择一个整数 $k\space 1\le k\le N$ 作为序列长度，并且随意选择一个满足条件 $1=i_1<i_2<\dots<i_k<i_{k+1}=N+1$ 的整数序列 $(i_1,i_2,\dots,i_k,i_{k+1})$。
• 对于每个满足 $1\le n\le k$ 的整数 $n$，第 $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 \space K$

$A_1 \space A_2 \space \dots \space A_N$

输出格式

请输出答案模 $998244353$ 的结果。

输入输出样例 #1

输入 #1

3 3
1 2 3

输出 #1

2

输入输出样例 #2

输入 #2

5 0
0 0 0 0 0

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

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$ 种划分方案。

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

Author: Redshift_Shine