Just Jump - 题解

标签与难度

标签: 动态规划, 组合数学, 容斥原理, 前缀和优化难度: 2200

题目大意喵~

各位勇者，下午好喵~！今天我们要解决一个有趣的跳跃问题，呐。

想象一下，我们站在一条长长的石板路上，起点是位置 0，终点是宝藏所在的 L。路上有 L-1 个石墩，分别在位置 1, 2, ..., L-1。

我们的跳跃规则是：

从当前位置 x，下一次必须跳到 y，并且 y >= x + d。也就是说，每一步至少要向前跳 d 的距离，不能后退或者原地踏步哦！
最后一次跳跃必须正好落在位置 L 上，不能多也不能少，不然就会被宝藏守护者发现，然后……啊呜一口吃掉！Σ(っ °Д °;)っ
最麻烦的是，有 m 个“陷阱”。每个陷阱用 (t, p) 表示，意思是我们的第 t 次跳跃，终点不能是位置 p。

我们的任务就是计算，在遵守所有这些规则的情况下，从 0 跳到 L 一共有多少种不同的跳跃方案。结果要对 998244353 取模，喵~

一个方案指的是一个跳跃序列，比如 0 -> p_1 -> p_2 -> ... -> L。只要其中任何一步的目的地不同，就算作是不同的方案。

解题思路分析

这道题看起来有点复杂，因为它混合了动态规划和带限制条件的计数，喵~。不过别怕，咱们可以一步一步把它拆解开来！

Part 1: 如果没有陷阱，该怎么跳？

首先，我们来思考一个简化版的问题：假如没有任何陷阱，那该怎么计算方案数呢？

这是一个经典的动态规划问题！我们可以定义 dp[i] 为跳到位置 i 的总方案数。

要想到达位置 i，我们肯定是从某个位置 j 跳过来的。根据规则，i >= j + d，也就是说 j <= i - d。所以，所有能跳到 i 的前一个位置 j 都满足 0 <= j <= i - d。

因此，dp[i] 就等于所有可以跳到它的位置 j 的方案数之和：

dp[i] = \sum_{j=0}^{i-d} dp[j]

这个转移方程如果每次都循环求和，效率太低了，会是 $O(L^2)$ ，对于 $L=10^7$ 肯定会超时的说。

但是！我们发现这个求和是一个连续区间的和。这种时候，我的直觉告诉我们——前缀和优化！

我们定义一个前缀和数组 prefix_sum[k] = dp[0] + dp[1] + ... + dp[k]。那么，上面的转移方程就可以变成：

dp[i] = \text{prefix\_sum}[i-d]

而前缀和数组本身的更新也很简单：prefix_sum[i] = prefix_sum[i-1] + dp[i]。

这样，我们就可以在 $O(L)$ 的时间复杂度内，计算出没有任何陷阱时，跳到任意位置的方案数了！最终答案就是 dp[L]。

状态定义: dp[i] 是跳到位置 i 的方案数。
初始条件: dp[0] = 1 （我们本来就在起点，这算一种方案），prefix_sum[0] = 1。
转移方程:
- dp[i] = prefix_sum[i-d] (当 i >= d 时)
- prefix_sum[i] = (prefix_sum[i-1] + dp[i]) % mod

Part 2: 加上烦人的陷阱！

现在，我们把陷阱加回来。陷阱 (t, p) 的限制是关于跳跃次数 t 的，而我们刚才的 dp 状态里只有位置信息，没有次数信息。如果强行加一维 dp[k][i] 表示跳 k 次到位置 i，状态空间太大，行不通呢。

当限制条件很少（m 只有 3000），而总方案数很多时，一个强大的思想就派上用场了——容斥原理！

总方案数 = (没有任何限制的总方案数) - (不合法的方案数)。

不合法的方案，就是至少经过一个陷阱的方案。根据容斥原理，我们有：不合法方案数 = (经过陷阱1的方案) + (经过陷阱2的方案) + ... - (同时经过陷阱1和2的方案) - ... + ...

直接用容斥公式会非常复杂。不过，我们可以用一种更巧妙的 DP 形式来处理容斥问题。

首先，我们把所有 m 个陷阱 (t_i, p_i) 按照跳跃次数 t_i 从小到大排序。如果 t_i 相同，就按位置 p_i 从小到大排序。

我们定义 g[i] 为：从起点 (0, 0) (0次跳跃在位置0) 出发，到达陷阱 i 描述的 (t_i, p_i) 状态（即第 t_i 次跳跃落在 p_i），并且中途没有经过任何其他排在 i 前面的陷阱 j (j < i) 的方案数。

g[i] 的计算方法如下：

先计算所有能到达 (t_i, p_i) 的路径总数，不管中途经过了什么。
减去那些不符合 g[i] 定义的路径，也就是中途经过了某个陷阱 j (j < i) 的路径。

如何计算从 (t_a, p_a) 跳到 (t_b, p_b) 的方案数呢？ 这相当于要在 t_b - t_a 次跳跃中，前进 p_b - p_a 的距离，并且每次跳跃至少为 d。假设每次跳跃的距离分别是 $x_1, x_2, \dots, x_{k}$ ，其中 $k = t_b - t_a$ 。我们有：

$x_1 + x_2 + \dots + x_k = p_b - p_a$
$x_j \ge d$ for all $j=1, \dots, k$

这是一个经典的组合数学问题，可以用“隔板法”或者叫“星星与木棍”来解决！我们让每个 $x_j$ 先减去 d-1，变成 $y_j = x_j - (d-1) \ge 1$ 。 $(y_1 + d - 1) + \dots + (y_k + d - 1) = p_b - p_a$ $y_1 + \dots + y_k = (p_b - p_a) - k \cdot (d-1)$ 现在问题变成了将 (p_b - p_a) - k * (d-1) 个小球分成 k 组，每组至少一个。方案数是 $C(\text{总数}-1, \text{组数}-1)$ 。即 $C((p_b - p_a) - k(d-1) - 1, k-1)$ 。

换个角度，令 $z_j = x_j - d \ge 0$ 。 $z_1 + \dots + z_k = (p_b - p_a) - k \cdot d$ 这是将 (p_b-p_a) - k*d 个小球分给 k 个盒子，允许空盒。方案数是 $C(\text{总数}+\text{组数}-1, \text{组数}-1)$ 。即 $C((p_b - p_a) - k \cdot d + k - 1, k - 1)$ 。这个公式更直观，我们就用它吧！记作 count_ways(delta_p, delta_t, d)。

所以，g[i] 的递推式就是：

g[i] = \text{count\_ways}(p_i, t_i, d) - \sum_{j=1}^{i-1} g[j] \times \text{count\_ways}(p_i - p_j, t_i - t_j, d)

这里的 count_ways(p_i, t_i, d) 指的是从 (0,0) 到 (t_i, p_i) 的方案数。我们遍历所有在 i 之前的陷阱 j。如果一条路径先经过了 j (这是它第一个经过的陷阱，方案数为 g[j])，然后再从 j 跳到 i，那么这条路径就算重了，需要减掉。

Part 3: 合并一切！

现在我们有了两大利器：

dp[i]：在没有陷阱的情况下，跳到位置 i 的方案数。
g[i]：第一次踩到陷阱 i 的方案数。

总的合法方案数 = (无限制总方案数) - (所有不合法方案数)

一个不合法方案，必然是第一次踩中了某个陷阱 i，然后从那里继续跳到了终点 L。

从起点到第一次踩中陷阱 i (即在 t_i 次跳跃后到达 p_i)，方案数是 g[i]。
从位置 p_i 跳到终点 L，还需要走 L - p_i 的距离。这个子问题的方案数，就是我们 Part 1 中计算的 dp[L - p_i]！

所以，所有第一次踩中陷阱 i 的完整非法路径有 g[i] * dp[L - p_i] 条。我们将所有陷阱 i 对应的非法路径数加起来，就得到了总的非法路径数。

最终的答案就是：

\text{Ans} = dp[L] - \sum_{i=1}^{m} g[i] \times dp[L - p_i]

记得每一步减法都要 ( ... % mod + mod) % mod 防止出现负数哦！

算法总结喵

预处理：计算阶乘和阶乘逆元，用于快速计算组合数 $C(n,k)$ 。
基础DP：计算 dp 数组，即无限制条件下跳到各点的方案数。 $O(L)$ 。
排序：将 m 个陷阱按 (t, p) 双关键字排序。
容斥DP：计算 g 数组。 $O(m^2)$ 。
合并计算：利用 dp 和 g 数组，根据最终公式计算答案。 $O(m)$ 。

总复杂度为 $O(L + m^2)$ ，可以稳稳地通过啦！

代码实现

cpp

#include <iostream>
#include <vector>
#include <algorithm>

// 使用一个好听的名字空间，喵~
namespace MeowAlgorithm {

// 定义常量
const int MOD = 998244353;
const int MAX_L = 10000005;
const int MAX_M = 3005;

// 阶乘和阶乘逆元数组
long long fact[MAX_L];
long long invFact[MAX_L];

// 陷阱结构体
struct Attack {
    int t, p;
    // 为了排序方便，重载小于号
    bool operator<(const Attack& other) const {
        if (t != other.t) {
            return t < other.t;
        }
        return p < other.p;
    }
};

// 快速幂，用来求逆元
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 预计算阶乘和逆元
void precompute_factorials(int n) {
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    invFact[n] = power(fact[n], MOD - 2);
    for (int i = n - 1; i > 0; --i) {
        invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
    }
}

// 计算组合数 C(n, k)
long long nCr_mod_p(long long n, long long k) {
    if (k < 0 || k > n) {
        return 0;
    }
    return (((fact[n] * invFact[k]) % MOD) * invFact[n - k]) % MOD;
}

// "星星与木棍" 组合计数函数
// 计算在 delta_t 次跳跃中，前进 delta_p 距离，每次至少跳 d 的方案数
long long count_path_ways(long long delta_p, long long delta_t, int d) {
    if (delta_t == 0) {
        return delta_p == 0 ? 1 : 0;
    }
    // 必须满足总距离不小于最小跳跃距离之和
    if (delta_p < delta_t * d) {
        return 0;
    }
    long long remaining_dist = delta_p - delta_t * d;
    return nCr_mod_p(remaining_dist + delta_t - 1, delta_t - 1);
}

void solve() {
    int L, d, m;
    std::cin >> L >> d >> m;

    std::vector<Attack> attacks(m);
    for (int i = 0; i < m; ++i) {
        std::cin >> attacks[i].t >> attacks[i].p;
    }

    // 预计算阶乘到 L+m，一个安全的上界
    precompute_factorials(L + m);

    // Part 1: 计算无限制时的 dp 数组
    std::vector<long long> dp_no_attack(L + 1, 0);
    std::vector<long long> prefix_sum(L + 1, 0);
    
    dp_no_attack[0] = 1;
    prefix_sum[0] = 1;
    for (int i = 1; i <= L; ++i) {
        if (i >= d) {
            dp_no_attack[i] = prefix_sum[i - d];
        }
        prefix_sum[i] = (prefix_sum[i - 1] + dp_no_attack[i]) % MOD;
    }

    // Part 2: 容斥 DP
    std::sort(attacks.begin(), attacks.end());

    std::vector<long long> g(m); // g[i] 是第一次踩到陷阱 i 的方案数
    long long total_ans = dp_no_attack[L];

    for (int i = 0; i < m; ++i) {
        // 计算从 (0,0) 到 (t_i, p_i) 的总方案数
        g[i] = count_path_ways(attacks[i].p, attacks[i].t, d);

        // 减去中途经过其他陷阱的方案
        for (int j = 0; j < i; ++j) {
            if (attacks[j].p >= attacks[i].p) continue; // 无法从更远或相同位置跳到当前位置
            
            long long ways_from_j_to_i = count_path_ways(attacks[i].p - attacks[j].p, attacks[i].t - attacks[j].t, d);
            long long to_subtract = (g[j] * ways_from_j_to_i) % MOD;
            g[i] = (g[i] - to_subtract + MOD) % MOD;
        }

        // 从总答案中减去这些不合法的路径
        long long ways_from_p_to_L = (L - attacks[i].p >= 0) ? dp_no_attack[L - attacks[i].p] : 0;
        long long bad_paths = (g[i] * ways_from_p_to_L) % MOD;
        total_ans = (total_ans - bad_paths + MOD) % MOD;
    }

    std::cout << total_ans << std::endl;
}

} // namespace MeowAlgorithm

int main() {
    // 加速输入输出，让我跑得更快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    MeowAlgorithm::solve();
    return 0;
}

复杂度分析

时间复杂度: $O(L + m^2)$
- 预计算阶乘和逆元需要 $O(L+m)$ 的时间，我们这里统一为 $O(L)$ 。
- 计算 dp_no_attack 数组和其前缀和需要 $O(L)$ 的时间。
- 对 m 个陷阱排序需要 $O(m \log m)$ 的时间。
- 计算 g 数组的容斥DP部分，是一个双重循环，需要 $O(m^2)$ 的时间。
- 最后合并计算答案需要 $O(m)$ 。
- 综上，总的时间复杂度由最大的部分决定，即 $O(L + m^2)$ 。
空间复杂度: $O(L)$
- 阶乘和逆元数组占用了 $O(L)$ 的空间。
- dp_no_attack 和 prefix_sum 数组也占用了 $O(L)$ 的空间。
- attacks 和 g 数组占用了 $O(m)$ 的空间。
- 因此，总的空间复杂度是 $O(L)$ 。

知识点总结

这道题是多种算法思想的美妙结合，就像一杯混合果汁，好喝又有营养，喵~

动态规划 (Dynamic Programming): 解决无限制条件下的路径计数问题是DP的经典应用。
前缀和优化: 当DP转移依赖于一个连续区间的和时，前缀和是将其从 $O(N)$ 优化到 $O(1)$ 的不二法门。
组合数学 (Combinatorics): "星星与木棍"模型是解决"整数划分"问题的利器，在本题中用于计算两点间固定步数的路径方案。
容斥原理 (Inclusion-Exclusion Principle): 当处理带有"不能"、"禁止"这类否定性约束的计数问题时，容斥原理是核心思想。本题通过DP的方式巧妙地实现了容斥，避免了复杂的公式展开。

希望这篇题解能帮助你理解这道题的思路，喵~ 如果还有不懂的地方，随时可以再来问我哦！一起加油，成为更厉害的算法大师吧！

Just Jump - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

Part 1: 如果没有陷阱，该怎么跳？ ​

Part 2: 加上烦人的陷阱！ ​

Part 3: 合并一切！ ​

算法总结喵 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​