/ 
Time Limit: 2 sec / Memory Limit: 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