笔试时间：2025年8月23日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：小A吃饭

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

换而言之，给定三个数 n,m,k。请问有几个长度为 n 的序列 a₁,a₂,…,aₙ满足：

①1 ≤ aᵢ ≤ m（1 ≤ i ≤ n）

②|aᵢ - aᵢ₊₁| ≥ k（1 ≤ i < n）

答案对 998244353 取模。

输入描述

输入一行，三个正整数 n,m,k，1 ≤ n,m ≤ 1000，0 ≤ k < m

输出描述

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

样例输入

3 4 2

样例输出

10

参考题解

动态规划

C++：

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, m, k;
    if (!(cin >> n >> m >> k)) return 0;
    const long long MOD = 998244353;

    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));
    vector<long long> pre(m + 1, 0);

    for (int j = 1; j <= (int)m; ++j) dp[1][j] = 1;

    for (int i = 2; i <= (int)n; ++i) {
        pre[0] = 0;
        for (int j = 1; j <= (int)m; ++j) {
            pre[j] = (pre[j - 1] + dp[i - 1][j]) % MOD;
        }
        for (int j = 1; j <= (int)m; ++j) {
            if (k == 0) {
                dp[i][j] = pre[m] % MOD;
                continue;
            }
            long long s1 = 0, s2 = 0;
            if (j >= 1 + (int)k) {
                s1 = pre[j - (int)k];             // [1, j-k]
            }
            if (j <= (int)m - (int)k) {
                // [j+k, m] = pre[m] - pre[j+k-1]
                s2 = (pre[m] - pre[j + (int)k - 1]) % MOD;
                if (s2 < 0) s2 += MOD;
            }
            dp[i][j] = (s1 + s2) % MOD;
        }
    }

    long long ans = 0;
    for (int j = 1; j <= (int)m; ++j) {
        ans = (ans + dp[n][j]) % MOD;
    }
    cout << ans << '\n';
    return 0;
}

Java：

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

public class Main {
    static final long MOD = 998244353L;

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        int m = fs.nextInt();
        int k = fs.nextInt();

        long[][] dp = new long[n + 1][m + 1];
        long[] pre = new long[m + 1];

        for (int j = 1; j <= m; j++) dp[1][j] = 1;

        for (int i = 2; i <= n; i++) {
            pre[0] = 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] % MOD;
                    continue;
                }
                long s1 = 0, s2 = 0;
                if (j >= 1 + k) {
                    s1 = pre[j - k]; // [1, j-k]
                }
                if (j <= m - k) {
                    s2 = (pre[m] - pre[j + k - 1]) % MOD; // [j+k, m]
                    if (s2 < 0) s2 += MOD;
                }
                dp[i][j] = (s1 + s2) % MOD;
            }
        }

        long ans = 0;
        for (int j = 1; j <= m; j++) ans = (ans + dp[n][j]) % MOD;
        System.out.println(ans);
    }

    // ---- FastScanner ----
    static final class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= 32);
            if (c == '-') { sgn = -1; c = read(); }
            while (c > 32) { x = x * 10 + (c - '0'); c = read(); }
            return x * sgn;
        }
    }
}

Python：

n, m, k = map(int, input().split())
mod = 998244353
dp = [[0] * (m + 1) for _ in range(n + 1)]
pre = [0] * (m + 1)
for j in range(1, m + 1):
    dp[1][j] = 1
for i in range(2, n + 1):
    pre[0] = 0
    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] % mod
            continue
        s1 = 0
        if j >= 1 + k:
            s1