AT_abc253_e [ABC253E] Distance Sequence
题目描述
有多少个长度为 $N$ 的整数数列 $A=(A_1,\ldots,A_N)$ 满足以下所有条件？
- $1 \leq A_i \leq M$，其中 $1 \leq i \leq N$。
- $|A_i - A_{i+1}| \geq K$，其中 $1 \leq i \leq N-1$。
请注意，答案可能非常大，请输出答案对 $998244353$ 取模后的结果。
输入格式
输入以如下格式从标准输入中给出。
> $N$ $M$ $K$
输出格式
输出答案对 $998244353$ 取模后的结果。
说明/提示
## 限制条件
- $2 \leq N \leq 1000$
- $1 \leq M \leq 5000$
- $0 \leq K \leq M-1$
- 输入均为整数
## 样例解释 1
满足条件的数列如下，共有 $6$ 个。
- $(1,2)$
- $(1,3)$
- $(2,1)$
- $(2,3)$
- $(3,1)$
- $(3,2)$
## 样例解释 2
满足条件的数列如下，共有 $2$ 个。
- $(1,3,1)$
- $(3,1,3)$
## 样例解释 3
请输出答案对 $998244353$ 取模后的结果。
由 ChatGPT 4.1 翻译