思路是记忆化 + 树状数组优化

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, k, s, ci, a[100010];
int f[1010][5010];
const int mo = 998244353;
int d[1010][5010];
void add(int x, int y, int t){
	int yy = y;
	for (; x<=n; x+=x&-x){
		y = yy;
		for (; y<=m; y+=y&-y){
			d[x][y] += t;
			d[x][y] %= mo;
		}
	}
}
int query(int x, int y){
	int ret = 0;
	int yy = y;
	for (; x>0; x-=x&-x){
		y = yy;
		for (; y>0; y-=y&-y){
			ret += d[x][y];
			ret %= mo;
		}
	}
	return ret;
}
int dfs(int p, int x){
	if (x > m) return 0;
	if (p >= n) return 1;
	if (f[p][x] != -1) return f[p][x];
	int num = 0;
	if (x + k <= m) num += query(p+1, m) - query(p+1, x+k-1);
	if (x - k >= 1) num += query(p+1, x-k) - query(p+1, 0LL);
	if (num) return f[p][x] = num;
	int ret = 0;
	for (int i=x+k; i<=m; i++){
		ret += dfs(p+1, i);
		ret %= mo;
	}
	for (int i=x-k; i>=1; i--){
		ret += dfs(p+1, i);
		ret %= mo;
	}
	add(p, x, ret);
	return f[p][x] = ret;
}
signed main(){
	memset(f, -1, sizeof(f));
	scanf ("%lld%lld%lld", &n, &m, &k);
	for (int i=1; i<=m; i++){
		s += dfs(1, i);
		s %= mo;
	}
	printf ("%lld\n", s);
	return 0;
}