[AGC009C] Division into Two
题意翻译
给定 $n$ 个不同的整数，求将它们分成两个集合 $X,Y$，并且 $X$ 集合中任意两个数的差大于等于 $A$，$Y$ 集合中任意两个数的差大于等于 $B$ 的方案数。
感谢@wxgwxg 提供翻译
题目描述
[problemUrl]: https://atcoder.jp/contests/jrex2017/tasks/agc009_c
相異なる整数 $ N $ 個からなる集合があります。この集合の $ i $ 番目に小さい要素は $ S_i $ です。この集合を $ X,Y $ の $ 2 $ つの集合に分割し、
- $ X $ に属するどの相異なる $ 2 $ つの要素も、その差の絶対値が $ A $ 以上
- $ Y $ に属するどの相異なる $ 2 $ つの要素も、その差の絶対値が $ B $ 以上
になるようにしたいです。このような分割としてありうるものの個数を $ 10^9\ +\ 7 $ で割ったあまりを求めてください。ただし、$ X,Y $ のうち一方が空となるような分割も数えます。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ A $ $ B $ $ S_1 $ : $ S_N $
输出格式
条件を満たす分割の個数を $ 10^9\ +\ 7 $ で割ったあまりを出力せよ。
输入输出样例
输入样例 #1
5 3 7
1
3
6
9
12输出样例 #1
5输入样例 #2
7 5 3
0
2
4
7
8
11
15输出样例 #2
4输入样例 #3
8 2 9
3
4
5
13
15
22
26
32输出样例 #3
13输入样例 #4
3 3 4
5
6
7输出样例 #4
0说明
### 制約
- 入力はすべて整数である。
- $ 1\ ≦\ N\ ≦\ 10^5 $
- $ 1\ ≦\ A\ ,\ B\ ≦\ 10^{18} $
- $ 0\ ≦\ S_i\ ≦\ 10^{18}(1\ ≦\ i\ ≦\ N) $
- $ S_i\ <\ S_{i+1}(1\ ≦\ i\ ≦\ N\ -\ 1) $
### Sample Explanation 1
次の $ 5 $ 通りの分割方法があります。 - $ X= ${$ 1,6,9,12 $}, $ Y= ${$ 3 $} - $ X= ${$ 1,6,9 $}, $ Y= ${$ 3,12 $} - $ X= ${$ 3,6,9,12 $}, $ Y= ${$ 1 $} - $ X= ${$ 3,6,9 $}, $ Y= ${$ 1,12 $} - $ X= ${$ 3,6,12 $}, $ Y= ${$ 1,9 $}