P3439.第1题-小A吃饭
题目内容
小A很喜欢做饭,也很喜欢享用自己做的美食，但是小A希望每天吃的菜和前一天的口味不同，若两道菜的编号差不小于k，则小A认为这两道菜的口味是不同的，现在小A正在制定未来n天的食谐（第一天可以吃任何菜)，请问一共有几种合法的食谱。答案可能很大，输出结果请对998244353取模。
换而言之，给定三个数n,m,k。请问有几个长度为n的序列a1,a2,...an满足：
1.1≤ai≤m(1≤i≤n)
2.∣ai−ai+1∣≥k(1≤i≤n)
答案对998244353取模。
输入描述
输入一行，三个整数n,m,k
1≤n,m≤1000，0≤k<m
输出描述
输出一行正整数，表示答案
样例1
输入
3 4 2
输出
10
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
