解题思路

动态规划（DP）

定义 $dp[i][j]$ 表示第 $i$ 天吃菜 $j$（$1\leq j\leq m$）时的合法食谱数。

转移方程

• 第一天可以任意选，$dp[1][j]=1$。
• 后面每一天，$a_i$ 可以选 $j$，只要 $|a_{i-1} - j| \geq k$。
• $dp[i][j]=\sum_{t=1}^m$且$~~|t-j|\geq k~~dp[i-1][t]$

为了优化效率：

• 如果 $k=0$，没有限制，每一项都可以转移，$dp[i][j]=\sum_{t=1}^m dp[i-1][t]$

• 如果 $k>0$，$|t-j|\geq k$，可分两段累加：

  • $t\leq j-k$
  • $t\geq j+k$

可以使用前缀和优化，把枚举 $t$ 优化到 $O(1)$。

复杂度分析

• $O(nm)$，每一层 $j$ 只需前缀和 $O(1)$ 处理。

代码实现

Python 实现

MOD = 998244353

n, m, k = map(int, input().split())

dp = [ [0] * (m+2) for _ in range(n+1) ]
for j in range(1, m+1):
    dp[1][j] = 1

for i in range(2, n+1):
    # 前缀和
    pre = [0]*(m+2)
    for j in range(1, m+1):
        pre[j] = (pre[j-1] + dp[i-1][j]) % MOD
    for j in range(1, m+1):
        if k == 0:
            dp[i][j] = pre[m]
        else:
            # t <= j-k
            l1, r1 = 1, j-k
            # t >= j+k
            l2, r2 = j+k, m
            s = 0
            if r1 >= l1:
                s += pre[r1] - pre[l1-1]
            if r2 >= l2:
                s += pre[r2] - pre[l2-1]
            dp[i][j] = s % MOD

print(sum(dp[n][1:m+1]) % MOD)

Java 实现

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 998244353;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] t = br.readLine().split(" ");
        int n = Integer.parseInt(t[0]);
        int m = Integer.parseInt(t[1]);
        int k = Integer.parseInt(t[2]);
        int[][] dp = new int[n+1][m+2];
        for (int j = 1; j <= m; ++j) dp[1][j] = 1;
        for (int i = 2; i <= n; ++i) {
            int[] pre = new int[m+2];
            for (int j = 1; j <= m; ++j)
                pre[j] = (pre[j-1] + dp[i-1][j]) % MOD;
            for (int j = 1; j <= m; ++j) {
                if (k == 0) {
                    dp[i][j] = pre[m];
                } else {
                    int s = 0;
                    if (j - k >= 1) s = (s + pre[j - k]) % MOD;
                    if (j + k <= m) s = (s + pre[m] - pre[j + k - 1] + MOD) % MOD;
                    dp[i][j] = s;
                }
            }
        }
        int ans = 0;
        for (int j = 1; j <= m; ++j)
            ans = (ans + dp[n][j]) % MOD;
        System.out.println(ans);
    }
}

C++ 实现

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 998244353;
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> dp(n+1, vector<int>(m+2, 0));
    for (int j = 1; j <= m; ++j) dp[1][j] = 1;
    for (int i = 2; i <= n; ++i) {
        vector<int> pre(m+2, 0);
        for (int j = 1; j <= m; ++j)
            pre[j] = (pre[j-1] + dp[i-1][j]) % MOD;
        for (int j = 1; j <= m; ++j) {
            if (k == 0) {
                dp[i][j] = pre[m];
            } else {
                int s = 0;
                if (j-k >= 1) s = (s + pre[j-k]) % MOD;
                if (j+k <= m) s = (s + pre[m] - pre[j+k-1] + MOD) % MOD;
                dp[i][j] = s;
            }
        }
    }
    int ans = 0;
    for (int j = 1; j <= m; ++j)
        ans = (ans + dp[n][j]) % MOD;
    cout << ans << endl;
    return 0;
}

题目内容

小$A$很喜欢做饭,也很喜欢享用自己做的美食，但是小$A$希望每天吃的菜和前一天的口味不同，若两道菜的编号差不小于$k$，则小$A$认为这两道菜的口味是不同的，现在小$A$正在制定未来$n$天的食谐（第一天可以吃任何菜)，请问一共有几种合法的食谱。答案可能很大，输出结果请对$998244353$取模。

换而言之，给定三个数$n,m,k$。请问有几个长度为$n$的序列$a_1,a_2,...a_n$满足：

1.$1≤a_i≤m (1≤i≤n)$

2.$|a_i-a_{i+1}|≥k(1≤i≤n)$

答案对$998244353$取模。

输入描述

输入一行，三个整数$n,m,k$

$1≤n,m≤1000，0≤k<m$

输出描述

输出一行正整数，表示答案

样例1

输入

3 4 2

输出

10