第 4 题
题意分析
有 NNN 个格子排成一列，编号 111 到 NNN。从第 111 个格子出发，每一步可以选择一个步长 d∈Sd \in Sd∈S 跳到 i+di+di+d（不能越过 NNN）。集合 SSS 是 KKK 个互不相交区间 [L1,R1],…,[LK,RK][L_1, R_1], \dots, [L_K, R_K][L1 ,R1 ],…,[LK ,RK ] 的并集。
求从第 111 格走到第 NNN 格的不同方案数，答案对 998244353998244353998244353 取模。
关键约束：
* 2≤N≤2×1052 \le N \le 2 \times 10^52≤N≤2×105
* 1≤K≤101 \le K \le 101≤K≤10（区间数很少！）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路分析
状态设计
设 dp[i]dp[i]dp[i] = 从第 111 个格子走到第 iii 个格子的方案数。
* 初始：dp[1]=1dp[1] = 1dp[1]=1
* 目标：dp[N]dp[N]dp[N]
朴素转移（不够快）
dp[i]=∑d∈S, i−d≥1dp[i−d]dp[i] = \sum_{d \in S,\ i-d \ge 1} dp[i-d]dp[i]=∑d∈S, i−d≥1 dp[i−d]
集合 SSS 大小最多可能达到 NNN，每个 iii 需要 O(∣S∣)O(|S|)O(∣S∣) 转移，总复杂度 O(N⋅∣S∣)=O(N2)O(N \cdot |S|) = O(N^2)O(N⋅∣S∣)=O(N2)，会超时。
关键观察：S 是若干个连续区间的并
因为 S=⋃j=1K[Lj,Rj]S = \bigcup_{j=1}^{K} [L_j, R_j]S=⋃j=1K [Lj ,Rj ]，所以：
dp[i]=∑j=1K∑d=LjRjdp[i−d](要求 i−d≥1)dp[i] = \sum_{j=1}^{K} \sum_{d=L_j}^{R_j} dp[i-d] \quad (\text{要求 } i - d \ge 1)dp[i]=∑j=1K ∑d=Lj Rj dp[i−d](要求 i−d≥1)
内层是 dp[i−Rj],dp[i−Rj+1],…,dp[i−Lj]dp[i-R_j], dp[i-R_j+1], \dots, dp[i-L_j]dp[i−Rj ],dp[i−Rj +1],…,dp[i−Lj ] 这一段连续区间的和，可以用前缀和优化！
前缀和优化
定义 pre[i]=dp[1]+dp[2]+dots+dp[i]\text{pre}[i] = dp[1] + dp[2] + dots + dp[i]pre[i]=dp[1]+dp[2]+dots+dp[i]，pre[0]=0\text{pre}[0] = 0pre[0]=0。
对每个区间 [Lj,Rj][L_j, R_j][Lj ,Rj ]，把 *** 从 LjL_jLj 到 RjR_jRj 替换成下标 i−di-di−d 从 i−Rji-R_ji−Rj 到 i−Lji-L_ji−Lj ：
* 设 lo=max(1,i−Rj)\text{lo} = max(1, i - R_j)lo=max(1,i−Rj )，texthi=i−Ljtext{hi} = i - L_jtexthi=i−Lj
* 若 lo≤hi\text{lo} \le \text{hi}lo≤hi，则贡献为 pre[hi]−pre[lo−1]\text{pre}[\text{hi}] - \text{pre}[\text{lo} - 1]pre[hi]−pre[lo−1]
每个状态 O(K)O(K)O(K) 转移，总复杂度 O(NK)=2×106O(NK) = 2 \times 10^6O(NK)=2×106，轻松通过。
模运算注意点
减法可能产生负数，要先 + MOD 再取模：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现（逐行解释）
