← 返回题目列表

AtCoder · mujin_pc_2017_a

A. 机器人赛车

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

你正在开发青蛙形状的机器人,并决定让它们互相比赛。

首先,您放置了 N 机器人到数轴上。 这些机器人都有编号 1 通过 N。 机器人当前坐标 i is x_i。 在这里,所有 x_i 是整数,并且 0 < x_1 < x_2 < ... < x_N.

您将重复执行以下操作:

  • 在数轴上选择一个机器人。设机器人的坐标为 x。选择目标坐标 x-1 or x-2,未被其他机器人占用。机器人现在跳转到选定的坐标。

当机器人的坐标变为 0 或更少,机器人被认为已完成并将立即从数轴上删除。 您将重复该操作,直到所有机器人完成比赛。

根据您在操作中的选择, N 机器人可以以不同的顺序完成比赛。 可以有多少种不同的顺序 N 机器人完成比赛? 求出模数的答案 10^9+7.

约束

  • 2 ≤ N ≤ 10^5
  • x_i 是一个整数。
  • 0 < x_1 < x_2 < ... < x_N ≤ 10^9

部分分数

  • 在测试集中值得 500 点, N ≤ 8.

输入

输入由标准输入按以下格式给出:

N
x_1 x_2 ... x_N

输出

打印不同订单的数量 N 机器人可以完成比赛,模数 10^9+7.


示例输入 1

3
1 2 3

示例输出 1

4

三个机器人可以按照四种不同的顺序完成比赛:

  • (机器人 1 → 机器人 2 → 机器人 3)
  • (机器人 1 → 机器人 3 → 机器人 2)
  • (机器人 2 → 机器人 1 → 机器人 3)
  • (机器人 2 → 机器人 3 → 机器人 1)

示例输入 2

3
2 3 4

示例输出 2

6

三个机器人可以按照六种不同的顺序完成比赛:

  • (机器人 1 → 机器人 2 → 机器人 3)
  • (机器人 1 → 机器人 3 → 机器人 2)
  • (机器人 2 → 机器人 1 → 机器人 3)
  • (机器人 2 → 机器人 3 → 机器人 1)
  • (机器人 3 → 机器人 1 → 机器人 2)
  • (机器人 3 → 机器人 2 → 机器人 1)

例如,订单 (机器人 3 → 机器人 2 → 机器人 1) 可以实现如下图所示:

a55aed48a00614569d4844f39807e2fb.png

示例输入 3

8
1 2 3 5 7 11 13 17

示例输出 3

10080

示例输入 4

13
4 6 8 9 10 12 14 15 16 18 20 21 22

示例输出 4

311014372

记得打印答案模数 10^9+7。 这种情况不包含在部分分数的测试集中。