atcoder#ABC158F. [ABC158F] Removing Robots
[ABC158F] Removing Robots
题目描述
数直線上に、 から の番号のついた 個のロボットが置かれています。ロボット は座標 に存在し、起動すると だけ正の方向に移動し、移動を終えると同時に数直線上から取り除かれます。全てのロボットの移動速度は同じで、大きさは無視できます。
イタズラ好きの高橋君は、数直線上にロボットが残っている限り、好きなだけ以下の操作を行うことができます。( 回も行わないことも可能です)
- ロボットを つ選び起動する。移動中のロボットが存在するときは行えない。
ロボット が移動する過程で、数直線上の座標 以上 未満の範囲に残っている別のロボット と接触したら、ロボット も起動されて移動を開始します。この処理は再帰的に繰り返されます。
高橋君が操作を繰り返した後、数直線上に残っているロボットの組み合わせとして考えられるものは何通り存在するでしょうか。答えは非常に大きくなる場合があるので、 で割った余りを出力してください。
输入格式
入力は以下の形式で標準入力から与えられる。
输出格式
数直線上に残っているロボットの組み合わせとして考えられるものの個数を で割った余りを出力せよ。
题目大意
N个机器人,第i个机器人在Xi位置上,若一个机器人被激活,则它将向右移动Di,若途径别的机器人,则该机器人也将被激活,求可以得到多少个没被激活的机器人的集合(激活次数不限)(对998244353取模)。
2
1 5
3 3
3
3
6 5
-1 10
3 3
5
4
7 10
-10 3
4 3
-4 3
16
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
110
提示
制約
- 入力は全て整数である
Sample Explanation 1
数直線上に残っているロボットの組み合わせとしては、 の 通りが考えられます。 これらは次のように操作すると実現されます。 - 高橋君はロボットを起動しない。このとき、ロボット が残ります。 - 高橋君がロボット を起動する。このとき、ロボット が移動する過程でロボット を起動します。最終的にロボットは つも残っていません。もしくは、高橋君がロボット を起動した後ロボット を起動しても、ロボットが残っていない状態にすることができます。 - 高橋君がロボット を起動し、操作を終了する。このとき、ロボット が残ります。
Sample Explanation 2
数直線上に残っているロボットの組み合わせとしては、$ \{1,\ 2,\ 3\},\ \{1,\ 2\},\ \{2\},\ \{2,\ 3\},\ \{\} $ の 通りが考えられます。
Sample Explanation 3
どのロボットも他のロボットに影響しません。
Sample Explanation 4
組み合わせとして考えられるものの個数を で割った余りを出力することに注意してください。