AT_abc158_f [ABC158F] Removing Robots

题目描述

在数轴上，有 $N$ 个编号为 $1$ 到 $N$ 的机器人。机器人 $i$ 位于坐标 $X_i$，启动后会向正方向移动 $D_i$ 的距离，移动结束后会从数轴上消失。所有机器人的移动速度相同，且可以忽略机器人的体积。

只要数轴上还有机器人，调皮的高桥君可以进行任意多次如下操作（也可以一次都不进行）：

• 选择一个机器人并启动它。如果有机器人正在移动，则不能进行此操作。

当机器人 $i$ 移动时，如果在其移动路径 $[X_i, X_i + D_i)$ 上存在尚未启动的其他机器人 $j$，则机器人 $j$ 也会被启动并开始移动。这个过程会递归地持续下去。

高桥君多次操作后，数轴上可能剩下的机器人组合有多少种？由于答案可能非常大，请输出对 $998244353$ 取模的结果。

输入格式

输入通过标准输入给出，格式如下：

$N$
$X_1\ D_1$
$X_2\ D_2$
$\vdots$
$X_N\ D_N$

输出格式

请输出数轴上可能剩下的机器人组合数，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

2
1 5
3 3

输出 #1

3

输入输出样例 #2

输入 #2

3
6 5
-1 10
3 3

输出 #2

5

输入输出样例 #3

输入 #3

4
7 10
-10 3
4 3
-4 3

输出 #3

16

输入输出样例 #4

输入 #4

20
-8 1
26 4
0 5
9 1
19 4
22 20
28 27
11 8
-3 20
-25 17
10 4
-18 27
24 28
-11 19
2 27
-2 18
-1 12
-24 29
31 29
29 7

输出 #4

110

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $-10^9 \leq X_i \leq 10^9$
• $1 \leq D_i \leq 10^9$
• $X_i \neq X_j\ (i \neq j)$
• 所有输入均为整数

样例解释 1

数轴上可能剩下的机器人组合有 $3$ 种，分别为 $\{1, 2\}$、$\{1\}$、$\{\}$。实现方式如下：

• 高桥君不启动任何机器人，此时机器人 $\{1, 2\}$ 保留。
• 高桥君启动机器人 $1$，在其移动过程中会启动机器人 $2$，最终没有机器人剩下。或者，先启动机器人 $2$ 再启动机器人 $1$，也可以让所有机器人消失。
• 高桥君启动机器人 $2$ 并结束操作，此时机器人 $\{1\}$ 保留。

样例解释 2

数轴上可能剩下的机器人组合有 $5$ 种，分别为 $\{1, 2, 3\}$、$\{1, 2\}$、$\{2\}$、$\{2, 3\}$、$\{\}$。

样例解释 3

所有机器人互不影响。

样例解释 4

请注意，输出时需要对 $998244353$ 取模。

由 ChatGPT 4.1 翻译