Ex - Odd Steps
Editorial
/
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
以下の条件を全て満たす数列 X の総数を 998244353 で割った余りを求めてください。
- X の全ての項は正の奇数である。
- X の各項の総和は S に等しい。
- X の累積和には A_1, \dots, A_N のいずれも現れない。厳密には、各 i \, (1 \leq i \leq |X|) に対して Y_i = X_1 + \dots + X_i と定めたとき、1 \leq i \leq |X|, 1 \leq j \leq N を満たす全ての整数 i, j に対して Y_i \neq A_j が成り立つ。
制約
- 1 \leq N \leq 10^5
- 1 \leq A_1 \lt A_2 \lt \dots \lt A_N \lt S \leq 10^{18}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N S A_1 \ldots A_N
出力
答えを出力せよ。
入力例 1
3 7 2 4 5
出力例 1
3
以下の 3 通りが条件を満たします。
- (1, 5, 1)
- (3, 3, 1)
- (7)
入力例 2
5 60 10 20 30 40 50
出力例 2
37634180
入力例 3
10 1000000000000000000 1 2 4 8 16 32 64 128 256 512
出力例 3
75326268
Score : 600 points
Problem Statement
Find the number, modulo 998244353, of sequences X that satisfy all of the following conditions.
- Every term in X is a positive odd number.
- The sum of the terms in X is S.
- The prefix sums of X contain none of A_1, \dots, A_N. Formally, if we define Y_i = X_1 + \dots + X_i for each i, then Y_i \neq A_j holds for all integers i and j such that 1 \leq i \leq |X| and 1 \leq j \leq N.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq A_1 \lt A_2 \lt \dots \lt A_N \lt S \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N S A_1 \ldots A_N
Output
Print the answer.
Sample Input 1
3 7 2 4 5
Sample Output 1
3
The following three sequences satisfy the conditions.
- (1, 5, 1)
- (3, 3, 1)
- (7)
Sample Input 2
5 60 10 20 30 40 50
Sample Output 2
37634180
Sample Input 3
10 1000000000000000000 1 2 4 8 16 32 64 128 256 512
Sample Output 3
75326268