爬台阶

爬台阶

发布于 2023-03-09 | 分类于动态规划、 oi | 2分钟 | 417字数 | 浏览量：

题目描述

楼上有 $n$ 级台阶，其中有 $m$ 级台阶是不安全的。yhf一开始站在第 $0$ 级台阶上，希望最终走到第 $n$ 级台阶

yhf跨一步满足以下约束：

只能向前走
不能落脚在不安全的台阶上
最多迈 $k$ 级台阶
落脚点不能超过第 $n$ 级台阶

也就是说，若某一刻yhf站在第 $c$ 级台阶上，那么他下一步可以落脚的位置 $x$ 满足 $c < x \le min(c + k, n)$ 且第 $x$ 级台阶是安全的。那么，yhf有多少种方法走到第 $n$ 级台阶

输入格式

第一行三个整数 $n, m, k$ ，描述见上文

第二行 $m$ 个整数， $d_1, d_2 ,...,d_m$ ，其中 $1 \le d_i < n$ ，表示不安全台阶的编号

输出格式

一个整数，模 $998244353$ 后的方案数

测试样例

样例输入

5 1 2
3

样例输出

数据规模

对于 $100 \%$ 的数据， $1 \le m < n \le 10^6, 1 \le k \le 10^6$

#include <bits/stdc++.h>
using namespace std;
#define N 1000002
int sum[N], mod = 998244353, n, m, k, t;
bool d[N];  // 默认是false

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; ++i)
        scanf("%d", &t), d[t] = true;
    for (int i = 1; i <= n; ++i) {
        t = 0;
        if (!d[i]) {
            if (i <= k)
                t = (sum[i - 1] + 1 + mod) % mod;
            else
                t = (sum[i - 1] - sum[i - k - 1] + mod) % mod;
        }
        sum[i] = (t % mod + sum[i - 1]) % mod;
    }
    cout << (sum[n] - sum[n - 1] + mod) % mod;
}