题目详情题解（0）讨论（0）提交记录（0）

AT_agc009_c.[AGC009C] Division into Two

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个包含 NN 个互不相同整数的集合。该集合中第 ii 小的元素为 SiS_i。现在要将这个集合划分为 XX 和 YY 两个集合，使得：

  • 属于 XX 的任意两个不同元素，其差的绝对值不少于 AA；
  • 属于 YY 的任意两个不同元素，其差的绝对值不少于 BB。

请计算满足上述条件的划分方法数，并对 109+710^9+7 取模输出。注意，允许 XX 或 YY 为空集。

输入格式

输入以如下格式从标准输入读入：

NN AA BB S1S_1 S2S_2 …\ldots SNS_N

输出格式

输出满足条件的划分方法数，对 109+710^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≤1051 \leq N \leq 10^5
  • 1≤A,B≤10181 \leq A, B \leq 10^{18}
  • 0≤Si≤1018 (1≤i≤N)0 \leq S_i \leq 10^{18}\ (1 \leq i \leq N)
  • Si<Si+1 (1≤i≤N−1)S_i < S_{i+1}\ (1 \leq i \leq N-1)

样例解释 1

有如下 55 种划分方法：

  • X={1,6,9,12}X=\{1,6,9,12\}，Y={3}Y=\{3\}
  • X={1,6,9}X=\{1,6,9\}，Y={3,12}Y=\{3,12\}
  • X={3,6,9,12}X=\{3,6,9,12\}，Y={1}Y=\{1\}
  • X={3,6,9}X=\{3,6,9\}，Y={1,12}Y=\{1,12\}
  • X={3,6,12}X=\{3,6,12\}，Y={1,9}Y=\{1,9\}

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页