思路：根据数据范围还有题目所处的位置我们可以联想到该题可以用dp来求解，我们设dp[i][j]代表第i个数为j时的方案数，dp[i][j]应为dp[i - 1][t] (t <= j - k) 和dp[i - 1][j + k]转移过来,如果我们不做任何优化的话n* m * n是肯定超时的，因此我们可以利用前缀和来求解两段的方案数,对于前缀和当n等于1时我们是可以确定地sum[i] = sum[i - 1] + 1,但是题目中k可以为0，当k等于0时左右两段是有重复点地，因此我们只需要计算一次即可，最终是求地总的方案数因此我们直接输出sum[m]即可，转换着求也挺难想地，而不是直接由dp求出，下面给出AC代码：

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int M = 1e9 + 7;
const int MOD = 998244353;
typedef long long ll;
typedef pair<ll,ll>PII;
typedef pair<char, int>PCI;ll n, m, k;ll dp[1010][5050];//第i个数为j的总的方案数
ll sum[N];
//dp[i][j] = dp[i - 1][j] + pre[j - k] + pre[m] - pre[j + k - 1];//后缀用总的 - 前缀
int main()
{cin >> n >> m >> k;for(int i = 1; i <= m; i ++){sum[i] = sum[i - 1] + 1;} //初始化本身也是一个for(int i = 2; i <= n; i ++){for(int j = 1; j <= m; j ++){if(j + k <= m){dp[i][j] = (dp[i][j] + ((sum[m] - sum[j + k - 1]) % MOD + MOD) % MOD) % MOD;}//用前缀和在dp过程中来优化是真的不好想if(j - k >= 1){if(k == 0){dp[i][j] = (dp[i][j] + sum[j - k - 1] % MOD) % MOD;}//等于0时左右两段就会有重复deelse {dp[i][j] = (dp[i][j] + sum[j - k] % MOD) % MOD;}}}//预处理前缀和memset(sum, 0, sizeof sum);for(int j = 1; j <= m; j ++){sum[j] = (sum[j - 1] + dp[i][j]) % MOD;}}cout << sum[m] % MOD << endl;return 0;
}