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