第 4 题

题意分析

有 $N$ 个格子排成一列，编号 $1$ 到 $N$。从第 $1$ 个格子出发，每一步可以选择一个步长 $d \in S$ 跳到 $i+d$（不能越过 $N$）。集合 $S$ 是 $K$ 个互不相交区间 $[L_1, R_1], \dots, [L_K, R_K]$ 的并集。

求从第 $1$ 格走到第 $N$ 格的不同方案数，答案对 $998244353$ 取模。

关键约束：

• $2 \le N \le 2 \times 10^5$
• $1 \le K \le 10$（区间数很少！）

---

思路分析

状态设计

设 $dp[i]$ = 从第 $1$ 个格子走到第 $i$ 个格子的方案数。

• 初始：$dp[1] = 1$
• 目标：$dp[N]$

朴素转移（不够快）

$dp[i] = \sum_{d \in S,\ i-d \ge 1} dp[i-d]$

集合 $S$ 大小最多可能达到 $N$，每个 $i$ 需要 $O(|S|)$ 转移，总复杂度 $O(N \cdot |S|) = O(N^2)$，会超时。

关键观察：S 是若干个连续区间的并

因为 $S = \bigcup_{j=1}^{K} [L_j, R_j]$，所以：

$dp[i] = \sum_{j=1}^{K} \sum_{d=L_j}^{R_j} dp[i-d] \quad (\text{要求 } i - d \ge 1)$

内层是 $dp[i-R_j], dp[i-R_j+1], \dots, dp[i-L_j]$ 这一段连续区间的和，可以用前缀和优化！

前缀和优化

定义 $\text{pre}[i] = dp[1] + dp[2] + dots + dp[i]$，$\text{pre}[0] = 0$。

对每个区间 $[L_j, R_j]$，把 $d$ 从 $L_j$ 到 $R_j$ 替换成下标 $i-d$ 从 $i-R_j$ 到 $i-L_j$：

• 设 $\text{lo} = max(1, i - R_j)$，$text{hi} = i - L_j$
• 若 $\text{lo} \le \text{hi}$，则贡献为 $\text{pre}[\text{hi}] - \text{pre}[\text{lo} - 1]$

每个状态 $O(K)$ 转移，总复杂度 $O(NK) = 2 \times 10^6$，轻松通过。

模运算注意点

减法可能产生负数，要先 + MOD 再取模：

(prefix[hi] - prefix[lo-1] + MOD) % MOD

---

代码实现（逐行解释）

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

const int MOD = 998244353;   // 题目要求的模数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, K;
    cin >> N >> K;
    
    // 读入 K 个区间 [L_j, R_j]
    vector<int> L(K), R(K);
    for (int j = 0; j < K; j++) {
        cin >> L[j] >> R[j];
    }
    
    // dp[i] = 走到第 i 个格子的方案数
    // pre[i] = dp[1] + dp[2] + ... + dp[i]，pre[0] = 0
    vector<long long> dp(N + 1, 0);
    vector<long long> pre(N + 1, 0);
    
    // 初始状态：在第 1 个格子，方案数为 1
    dp[1] = 1;
    pre[1] = 1;
    
    // 从 i=2 开始递推
    for (int i = 2; i <= N; i++) {
        long long val = 0;
        
        // 枚举每个区间 [L_j, R_j]
        for (int j = 0; j < K; j++) {
            // 步长 d 在 [L_j, R_j] 范围内，对应 i-d 在 [i-R_j, i-L_j]
            // 同时要求 i-d >= 1，即下标至少为 1
            int lo = max(1, i - R[j]);   // 下标下界
            int hi = i - L[j];            // 下标上界
            
            // 只有当 lo <= hi 时区间才非空（即至少有一个合法的 d）
            if (lo <= hi) {
                // 用前缀和 O(1) 求 dp[lo] + dp[lo+1] + ... + dp[hi]
                // +MOD 是为了防止减法出现负数
                val = (val + pre[hi] - pre[lo - 1] + MOD) % MOD;
            }
        }
        
        dp[i] = val;
        pre[i] = (pre[i - 1] + dp[i]) % MOD;   // 更新前缀和
    }
    
    cout << dp[N] << endl;
    return 0;
}