#P17707. [ICPC 2019 Nanjing R] Space Station
[ICPC 2019 Nanjing R] Space Station
题目描述
企鹅星系中有 个空间站,编号从 到 。第 个空间站拥有所谓的能量,数量为 。
当你到达一个空间站时,你可以获得该站的全部能量。现在,你正位于第 号空间站,并且你已经获得了该站数量为 的能量。每次你只被允许移动到一个能量不超过你当前所拥有能量的空间站,而空间站之间的移动不会消耗你任何能量,这一点在计算中可以忽略不计。
现在,你决定恰好访问每个空间站一次。你完成整个旅程的不同方案有多少种?由于答案会非常巨大,你只需要求出方案数对 取模的结果。
输入格式
第一行包含一个整数 。
第二行包含 个整数 和 ,其中对于 有 。
输出格式
输出一行一个整数,表示访问所有空间站以完成旅程的不同方案数对 取模的结果。
3
2 1 2 3
4
5
1 1 1 1 2 3
54
提示
在第一个样例中,访问顺序可以是 、、 和 之一。然而,它不能是 或 。确实,当你从第 号空间站出发时,你仅仅获得了 单位的能量。然后你不被允许跳到第 号空间站,因为那儿的能量是 ,比你持有的要大。
翻译由 DeepSeek V4 Pro 完成