[R27G]山峰 - 代码源竞赛平台

时空限制

3S/512M

题目描述

给定一个长度为奇数 $n$ 的数组 $X_1, X_2, \ldots, X_n$，以及一个整数 $H$。 你的任务是，计算有多少个长度为 $n$ 的数组 $h_1, h_2, \ldots, h_n$ 满足以下所有条件：

1. 对于所有的 $1 \le i \le n$，都有 $0 \le h_i \le X_i$。
2. 序列所有元素之和不小于 $H$，即 $\sum_{i=1}^{n} h_i \ge H$。
3. 对于所有满足偶数下标 $i$，满足 $h_i \ge h_{i-1} + h_{i+1}$。

由于答案可能很大，请将结果对 $998244353$ 取模。

格式

输入格式

第一行包含两个整数 $n, H$。

第二行包含 $n$ 个整数 $X_1, X_2, \ldots, X_n$。具体意义如题目所示。

输出格式

输出一个整数，表示满足所有条件的序列 $h$ 的数量，对 $998244353$ 取模。

样例

样例输入 #1

3 8
3 5 3

样例输出 #1

12

样例解释 #1

符合条件的数组为：

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

数据规模

对于 $20\%$ 的数据，$3 \leq n \leq 5$，$1 \leq H \leq 50$，$1 \leq X_i \leq 10$。

对于 $40\%$ 的数据，$3 \leq n \leq 50$，$1 \leq H \leq 50$，$1 \leq X_i \leq 50$。

对于 $100\%$ 的数据，$3 \leq n \leq 300$，$1 \leq H \leq 700$，$1 \leq X_i \leq 500$。