分数: 475 点
问题陈述
给你一个序列 A = (A_1, A_2, \dots, A_N) 长度 N 和一个整数 K.
有 2^{N-1} 划分方法 A 分成几个连续的子序列。这些除法中有多少个没有子序列,其元素之和为 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-th 子序列是通过取 i_n-th 通过 (i_{n+1} - 1)第一个元素 A,维持秩序。
以下是一些划分示例 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