102587: [AtCoder]ABC258 Ex - Odd Steps
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
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
Input
题意翻译
给定 $ n, S $ 和序列 $ A_n $，求任意长度的满足以下条件的序列个数： * 仅由正奇数组成。 * 所有数之和为 $ S $。 * 序列的任意前缀和均不能为 $ A_n $ 中任意数。 答案对 $ 998244353 $ 取模。Output
得分：600分
部分
问题描述
求满足以下所有条件的序列$X$的数量，模$998244353$。
- $X$中的每个项都是正的奇数。
- $X$中项的和为$S$。
- $X$的前缀和中没有$A_1, \dots, A_N$。具体来说，如果对于每个$i$，我们定义$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
以下三个序列满足条件。
- $(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