← 返回题目列表

AtCoder · abc370_e

H. 避免 K 分区

中文机器翻译题面 查看原题

分数: 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