题目内容

小L想在一条走廊上安装一排彩灯，共有 $n$ 盏灯，可供选择的颜色有 $m$ 种，编号为 $1$ 到 $m$。为了让相邻彩灯的颜色产生足够的对比度，小L要求相邻彩灯的颜色编号之差的绝对值不小于 $k$。现在小L想知道，一共有多少种满足条件的配色方案。

形式化地，给定正整数 $n$、$m$ 和非负整数 $k$ ($k<m$)，求有多少个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$ 满足：

1. $1 \le a_i \le m$ ($1 \le i \le n$)；
2. $|a_i - a_{i+1}| \ge k$ ($1 \le i < n$)。

答案可能很大，请输出对 998244353 取模后的结果。

数据范围：$n$ 和 $m$ 均不超过 1000，$k$ 满足 $0 \le k < m$。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写