题目描述

难度分:$1073$

输入$n(2 \leq n \leq 1000)$，$m$，$k(0 \leq k \lt m \leq 5000)$。

输出有多少个长为$n$的数组，满足元素范围为$[1,m]$且$|a[i]-a[i+1]| \geq k$。

模$998244353$。

输入样例$1$

2 3 1

输出样例$1$

6

输入样例$2$

3 3 2

输出样例$2$

2

输入样例$3$

100 1000 500

输出样例$3$

657064711

算法

动态规划+前缀和优化

状态定义

$dp[i][cur]$表示仅考虑前$i$个元素，且以$cur$结尾的数组中，满足限制的数组个数。

状态转移

base case：第一个数满足$dp[1][k]=1$（$k \in [1, m]$），可以在值域中取任意值。
一般情况：当前数为$cur \in [1,m]$，那么前一个数为$pre \in [1,cur-k] \cup [cur+k,m]$，状态转移方程为

$dp[i][cur]=\Sigma_{pre=1}^{cur-k}dp[i-1][pre] + \Sigma_{cur+k}^{m}dp[i-1][pre]$

直接枚举$pre$的话时间复杂度是$O(nm^2)$的，会超时。利用前缀和优化可以快速求得状态转移方程中的求和结果（计算当前行的前缀和供下一行的状态转移使用），从而将时间复杂度控制在$O(nm)$。

复杂度分析

时间复杂度

DP是个双重循环，时间复杂度为$O(nm)$。

空间复杂度

开辟了$n \times m$的DP数组和前缀和数组，额外空间复杂度为$O(nm)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010, M = 5010, MOD = 998244353;
int n, m, k;
int dp[N][M], presum[N][M];

int windowSum(int i, int l, int r) {
    if(l > r) return 0;
    return (presum[i][r] - presum[i][l - 1] + MOD) % MOD;
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    memset(dp, 0, sizeof dp);
    memset(presum, 0, sizeof presum);
    for(int i = 1; i <= m; i++) {
        dp[1][i] = 1;
        presum[1][i] = (presum[1][i - 1] + dp[1][i]) % MOD;
    }
    for(int i = 2; i <= n; i++) {
        for(int cur = 1; cur <= m; cur++) {
            if(k == 0) dp[i][cur] = windowSum(i - 1, 1, m);     // 注意k=0
            else dp[i][cur] = (windowSum(i - 1, 1, cur - k) + windowSum(i - 1, cur + k, m)) % MOD;
            presum[i][cur] = (presum[i][cur - 1] + dp[i][cur]) % MOD;
        }
    }
    printf("%d\n", windowSum(n, 1, m));
    return 0;
}