Distance Sequence

题目描述

有多少个长度为 $N$ 的整数序列 $A=(A_1,\ldots,A_N)$ 满足以下所有条件？

$1\le A_i \le M$ $(1 \le i \le N)$

$|A_i - A_{i+1}| \geq K$ $(1 \le i \le N - 1)$

由于计数可能非常大，请把答案对 $998244353$ 取模后输出。

输入格式

输入从标准输入按如下格式给出： $N$ $M$ $K$

输出格式

输出对 $998244353$ 取模的计数。

2 3 1

6

3 3 2

2

100 1000 500

657064711

提示

$2 \leq N \leq 1000$ $1 \leq M \leq 5000$ $0 \leq K \leq M-1$ 输入中的所有数值均为整数。以下 $6$ 个序列满足条件。

$(1,2)$ $(1,3)$ $(2,1)$ $(2,3)$ $(3,1)$ $(3,2)$
以下 $2$ 个序列满足条件。

$(1,3,1)$ $(3,1,3)$
把答案对 $998244353$ 取模后输出。

标签: AtCoder|abc253E

来源

AtCoder|abc253E