33OJ
登录 注册

#P17707. [ICPC 2019 Nanjing R] Space Station

    ID: 20159 远端评测题 3000ms 512MiB 尝试: 0 已通过: 0 显示难度提高 上传者: 标签>暴力数据结构2019记忆化搜索ICPCAd-hoc南京

[ICPC 2019 Nanjing R] Space Station

题目描述

企鹅星系中有 n+1n+1 个空间站,编号从 00 到 nn。第 ii 个空间站拥有所谓的能量,数量为 aia_i。

当你到达一个空间站时,你可以获得该站的全部能量。现在,你正位于第 00 号空间站,并且你已经获得了该站数量为 a0a_0 的能量。每次你只被允许移动到一个能量不超过你当前所拥有能量的空间站,而空间站之间的移动不会消耗你任何能量,这一点在计算中可以忽略不计。

现在,你决定恰好访问每个空间站一次。你完成整个旅程的不同方案有多少种?由于答案会非常巨大,你只需要求出方案数对 109+710^9+7 取模的结果。

输入格式

第一行包含一个整数 n (1≤n≤105)n~(1 \le n \le 10^5)。

第二行包含 n+1n+1 个整数 a0,a1,a2,⋯ ,an−1a_0, a_1, a_2, \cdots, a_{n-1} 和 ana_n,其中对于 i∈{0,1,2,⋯ ,n}i \in \{0, 1, 2, \cdots, n\} 有 0≤ai≤500 \le a_i \le 50。

输出格式

输出一行一个整数,表示访问所有空间站以完成旅程的不同方案数对 109+710^9+7 取模的结果。

3
2 1 2 3
4
5
1 1 1 1 2 3
54

提示

在第一个样例中,访问顺序可以是 [0,1,2,3][0,1,2,3]、[0,1,3,2][0,1,3,2]、[0,2,1,3][0,2,1,3] 和 [0,2,3,1][0,2,3,1] 之一。然而,它不能是 [0,3,1,2][0,3,1,2] 或 [0,3,2,1][0,3,2,1]。确实,当你从第 00 号空间站出发时,你仅仅获得了 22 单位的能量。然后你不被允许跳到第 33 号空间站,因为那儿的能量是 33,比你持有的要大。

翻译由 DeepSeek V4 Pro 完成