MEX counting

题意翻译

给定 $n$ 和 $k$ 和一个长度为 $n$ 的整数序列 $b$ 。 求有多少个长度为 $n$ 的序列 $a$ 满足对于任意的 $1 \le i \le n$ 都有： - $0 \le a_i \le n$ - $|MEX(a_1,a_2,\dots,a_i)-b_i| \le k$ 其中 $MEX(c)$ 表示 $c$ 中没出现过的最小的非负整数。 答案对 $998244353$ 取模 $n \le 2000$ , $k \le 50$

题目描述

For an array $ c $ of nonnegative integers, $ MEX(c) $ denotes the smallest nonnegative integer that doesn't appear in it. For example, $ MEX([0, 1, 3]) = 2 $ , $ MEX([42]) = 0 $ . You are given integers $ n, k $ , and an array $ [b_1, b_2, \ldots, b_n] $ . Find the number of arrays $ [a_1, a_2, \ldots, a_n] $ , for which the following conditions hold: - $ 0 \le a_i \le n $ for each $ i $ for each $ i $ from $ 1 $ to $ n $ . - $ |MEX([a_1, a_2, \ldots, a_i]) - b_i| \le k $ for each $ i $ from $ 1 $ to $ n $ . As this number can be very big, output it modulo $ 998\,244\,353 $ .

输入输出格式

输入格式

The first line of the input contains two integers $ n, k $ ( $ 1 \le n \le 2000 $ , $ 0 \le k \le 50 $ ). The second line of the input contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ -k \le b_i \le n+k $ ) — elements of the array $ b $ .

输出格式

Output a single integer — the number of arrays which satisfy the conditions from the statement, modulo $ 998\,244\,353 $ .

输入输出样例

输入样例 #1

4 0
0 0 0 0

输出样例 #1

256

输入样例 #2

4 1
0 0 0 0

输出样例 #2

431

输入样例 #3

4 1
0 0 1 1

输出样例 #3

509

输入样例 #4

5 2
0 0 2 2 0

输出样例 #4

6546

输入样例 #5

3 2
-2 0 4

输出样例 #5

11