H - Avoid K Partition 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 475 点

問題文

長さ N の数列 A = (A_1, A_2, \dots, A_N) および整数 K があります。
A をいくつかの連続部分列に分割する方法は 2^{N-1} 通りありますが、そのうち分割後に要素の和が K である列が存在しない分割の方法は何通りありますか。答えを 998244353 で割った余りを求めてください。

ここで、「A をいくつかの連続部分列に分割する」とは次の手順のことを言います。

  • 分割後の数列の個数 k (1 \leq k \leq 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 \leq n \leq 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)

制約

  • 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

問題文の条件を満たす分割は次の 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

Score : 475 points

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N and an integer K.
There are 2^{N-1} ways to divide A into several contiguous subsequences. How many of these divisions have no subsequence whose elements sum to K? Find the count modulo 998244353.

Here, "to divide A into several contiguous subsequences" means the following procedure.

  • Freely choose the number k (1 \leq k \leq N) of subsequences and an integer sequence (i_1, i_2, \dots, i_k, i_{k+1}) satisfying 1 = i_1 \lt i_2 \lt \dots \lt i_k \lt i_{k+1} = N+1.
  • For each 1 \leq n \leq k, the n-th subsequence is formed by taking the i_n-th through (i_{n+1} - 1)-th elements of A, maintaining their order.

Here are some examples of divisions for A = (1, 2, 3, 4, 5):

  • (1, 2, 3), (4), (5)
  • (1, 2), (3, 4, 5)
  • (1, 2, 3, 4, 5)

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • -10^{15} \leq K \leq 10^{15}
  • -10^9 \leq A_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the count modulo 998244353.

Sample Input 1

3 3
1 2 3

Sample Output 1

2

There are two divisions that satisfy the condition in the problem statement:

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

Sample Input 2

5 0
0 0 0 0 0

Sample Output 2

0

Sample Input 3

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

Sample Output 3

428