2729: T4-遥控炸弹
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：25
解决：1
题目描述
梦国和熊国之间发生了一场大战。
梦国的武器研究员梦梦发现，士兵在投掷炸弹的时候，总是会误伤友方人员，所以他们发明了一种遥控炸弹，这种炸弹只会**在前方的一定范围**爆炸，即假设该炸弹位于 $x$ 位置，其威力为 $d$，那么其爆炸范围为 $[x,x+d)$。
同时，为了加大炸弹的威力，梦梦设计了引爆程序，炸弹之间彼此会产生连锁反应，即如果第 $i$ 个炸弹被引爆，且第 $j$ 个炸弹在第 $i$ 个炸弹的爆炸范围内，那么炸弹 $j$ 也会同时被引爆。
为了形式化问题本身，我们假定所有炸弹都被安装在了数轴的整点上，所以如果一个炸弹位于 $x$ 位置，其威力为 $d$，那么其爆炸后会引爆 $x,x+1,x+2,…,x+d-1$ 这些位置上的炸弹。
现在数轴上有 $n$ 个炸弹，第 $i$ 个炸弹位于 $x_i$，其威力为 $d_i$，梦梦可以手动操控其中**若干个**炸弹并将其同时引爆，梦梦想知道通过连锁反应，最终被引爆的炸弹集合有多少种可能，答案对 $998244353$ 取模。
梦国的武器研究员梦梦发现，士兵在投掷炸弹的时候，总是会误伤友方人员，所以他们发明了一种遥控炸弹，这种炸弹只会**在前方的一定范围**爆炸，即假设该炸弹位于 $x$ 位置，其威力为 $d$，那么其爆炸范围为 $[x,x+d)$。
同时，为了加大炸弹的威力，梦梦设计了引爆程序，炸弹之间彼此会产生连锁反应，即如果第 $i$ 个炸弹被引爆，且第 $j$ 个炸弹在第 $i$ 个炸弹的爆炸范围内，那么炸弹 $j$ 也会同时被引爆。
为了形式化问题本身，我们假定所有炸弹都被安装在了数轴的整点上，所以如果一个炸弹位于 $x$ 位置，其威力为 $d$，那么其爆炸后会引爆 $x,x+1,x+2,…,x+d-1$ 这些位置上的炸弹。
现在数轴上有 $n$ 个炸弹，第 $i$ 个炸弹位于 $x_i$，其威力为 $d_i$，梦梦可以手动操控其中**若干个**炸弹并将其同时引爆，梦梦想知道通过连锁反应，最终被引爆的炸弹集合有多少种可能，答案对 $998244353$ 取模。
输入
输入第一行，包含一个正整数 $n$。
之后 $n$ 行，每行包含 $2$ 个整数，表示 $x_i,d_i$。
之后 $n$ 行，每行包含 $2$ 个整数，表示 $x_i,d_i$。
输出
输出共一行，包含一个整数，表示答案，答案对 $998244353$ 取模。
样例输入 复制
2
1 5
3 3样例输出 复制
3提示
### 样例解释1
若手动引爆炸弹 $\{1\}$，则最终被引爆的炸弹集合为 $\{1,2\}$。
若手动引爆炸弹 $\{1,2\}$，则最终被引爆的炸弹集合为 $\{1,2\}$。
若手动引爆炸弹 $\{2\}$，则最终被引爆的炸弹集合为 $\{2\}$。
若引爆炸弹 $\{\}$，则最终被引爆的炸弹集合为 $\{\}$。
所以共有 $3$ 种可能，分别为 $\{1,2\},\{2\},\{\}$。
### 样例输入2
```text
3
6 5
-1 10
3 3
```
### 样例输出2
```text
5
```
### 样例解释2
共有 $5$ 种可能，分别为 $\{1,2,3\},\{1\},\{\},\{1,3\},\{3\}$。
### 样例输入3
```text
4
7 10
-10 3
4 3
-4 3
```
### 样例输出3
```text
16
```
### 样例解释3
这些炸弹两两之间不会相互波及，所以手动引爆的结果即为最终炸弹引爆的结果，答案为 $2^4=16$。
### 样例输入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
```
### 评测数据规模
对于 $40\%$ 的数据，$1 \leq n \leq 20$。
对于 $60\%$ 的数据，$1 \leq n \leq 1000$
对于另外 $20\%$ 的数据，保证任意一个炸弹引爆后都不会发生连锁反应。
对于所有测评数据，$1 \leq n \leq 2 \times 10^5,-10^9 \leq x_i \leq 10^9,1 \leq d_i \leq 10^9$，保证炸弹的坐标两两不同。
若手动引爆炸弹 $\{1\}$，则最终被引爆的炸弹集合为 $\{1,2\}$。
若手动引爆炸弹 $\{1,2\}$，则最终被引爆的炸弹集合为 $\{1,2\}$。
若手动引爆炸弹 $\{2\}$，则最终被引爆的炸弹集合为 $\{2\}$。
若引爆炸弹 $\{\}$，则最终被引爆的炸弹集合为 $\{\}$。
所以共有 $3$ 种可能，分别为 $\{1,2\},\{2\},\{\}$。
### 样例输入2
```text
3
6 5
-1 10
3 3
```
### 样例输出2
```text
5
```
### 样例解释2
共有 $5$ 种可能，分别为 $\{1,2,3\},\{1\},\{\},\{1,3\},\{3\}$。
### 样例输入3
```text
4
7 10
-10 3
4 3
-4 3
```
### 样例输出3
```text
16
```
### 样例解释3
这些炸弹两两之间不会相互波及，所以手动引爆的结果即为最终炸弹引爆的结果，答案为 $2^4=16$。
### 样例输入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
```
### 评测数据规模
对于 $40\%$ 的数据，$1 \leq n \leq 20$。
对于 $60\%$ 的数据，$1 \leq n \leq 1000$
对于另外 $20\%$ 的数据，保证任意一个炸弹引爆后都不会发生连锁反应。
对于所有测评数据，$1 \leq n \leq 2 \times 10^5,-10^9 \leq x_i \leq 10^9,1 \leq d_i \leq 10^9$，保证炸弹的坐标两两不同。