猫空缆车是台北市的一个著名景点。这个缆车系统包括一个环形轨道、一个缆车站和 $n$ 个编号为 $1$ 到 $n$ 的缆车。这些缆车以固定的方向在轨道上循环运行。在缆车 $i$ 经过缆车站之后，下一个经过缆车站的缆车将会是 $i+1$ （$i<n$ 时），或者是缆车 $1$（$i=n$ 时）。

缆车可能会发生故障。幸运的是，我们有无限多个后备的空闲缆车，其编号依次为 $n+1,n+2$ 等等。当某个缆车发生故障时，我们会在轨道上的同一位置用最前一个空闲缆车替换它，也就是说，编号最小的空闲缆车。举个例子，如果当前有五辆缆车而缆车 $1$ 发生了故障，那么我们将用缆车 $6$ 来替换它。

你喜欢去缆车站上观察缆车过站。一个缆车序列是由缆车过站次序形成的 $n$ 个缆车编号的序列。在你到达缆车站之前，有可能会有一到多个缆车发生故障（并且被替换掉），但是在你观察过程中是不会有缆车发生故障的。

注意，在轨道上的相同一组缆车，有可能给出多种缆车序列，这取决于当你到缆车站时哪辆缆车最先过站。举个例子，如果没有任何缆车发生故障，那么 $(2,3,4,5,1)$ 和 $(4,5,1,2,3)$ 都可能是缆车序列，但是 $(4,3,2,5,1)$ 不可能是（因为缆车的次序有误）。

如果缆车 $1$ 发生故障，那么我们可能会观察到缆车序列 $(4,5,6,2,3)$。如果接着缆车 $4$ 发生故障而我们用缆车 $7$ 替换它，就有可能会观察到缆车序列 $(6,2,3,7,5)$。如果缆车 $7$ 在此后发生故障而我们用缆车 $8$ 替换它，那么现在就有可能会观察到缆车序列 $(3,8,5,6,2)$。

一个替换序列是一个由故障缆车编号组成的序列，其次序与故障发生次序相同。在前面的例子中，替换序列是 $(1,4,7)$。如果一个替换序列 $r$ 对应的故障发生后，我们由此有可能观察到缆车序列 $g$，就称替换序列 $r$ 生成缆车序列 $g$。

缆车序列检查

在前三个子任务中，你必须检查某个输入序列是否是一个缆车序列。下表举例说明了哪些序列是缆车序列而哪些不是。你需要实现一个函数 valid。

• valid(n, inputSeq)
  • $n$: 输入序列长度
  • inputSeq: 大小为 $n$ 的数组；inputSeq[i] 是输入序列的第 $i$ 个元素，其中 $0\le i\le n-1$。
  • 当输入序列是一个缆车序列时，函数应返回 $1$，否则返回 $0$。

子任务1, 2, 3

例子

替换序列

在接下来的三个子任务中，你必须构造一个能够生成给定缆车序列的可能的替换序列。满足条件的任意替换序列都可以。你需要实现一个函数 replacement。

• replacement(n, gondolaSeq, replacementSeq)
  • $n$ 是缆车序列的长度。
  • gondolaSeq: 大小为 $n$ 的数组；gondolaSeq 保证是一个缆车序列，而 gondolaSeq[i] 是序列中的第 $i$ 个元素，这里 $0\le i\le n-1$。
  • 函数应返回替换序列的长度 $l$。
  • replacementSeq: 一个足够大的能存下替换序列的数组；你应当将替换序列中的第 $i$ 个元素存放到 replacementSeq[i] 做为返回结果，这里 $0\le i\le l-1$。

子任务4, 5, 6

例子

替换序列计数

在接下来的四个子任务中，你必须计算所有能够生成给定序列（有可能是缆车序列，也有可能不是）的可能替换序列的数目，并将其对 $1000000009$ 取模。你需要实现一个函数 countReplacement。

• countReplacement(n, inputSeq)
  • $n$: 输入序列的长度。
  • inputSeq: 大小为 $n$ 的数组；inputSeq[i] 是输入序列的第 $i$ 个元素，其中 $0\le i\le n-1$。
  • 如果输入序列是一个缆车序列，则计算能够生成该缆车序列的可能的替换序列的数目（有可能会非常大），然后将该数值对 $1000000009$ 取模做为返回值。如果输入序列不是一个缆车序列，函数应返回 $0$。如果输入序列是一个缆车序列，但是没有缆车发生故障，函数应返回 $1$。

子任务7, 8, 9, 10

例子

实现细节

本题只支持 C/C++。

你只能提交一个源文件实现上述的函数，在该文件中应实现前面所述的三个函数（即便你只想解决其中的部分子任务，也要给出全部函数），并遵循下述命名与接口。你还需要包含头文件 gondola.h。

int valid(int n, int inputSeq[]);
int replacement(int n, int gondolaSeq[], int replacementSeq[]);
int countReplacement(int n, int inputSeq[]);

评测方式

评测系统将会读入如下格式的输入数据：

• 第 $1$ 行: $T$，你的程序需要解决的子任务编号（$1\le T\le 10$）。
• 第 $2$ 行: $n$，输入序列的长度。
• 第 $3$ 行: 如果 $T$ 是4、5或者6，此行包含 $\text{gondolaSeq[0]},\dots ,\text{gondolaSeq[n-1]}$。否则此行包含$\text{inputSeq[0]},\dots ,\text{inputSeq[n-1]}$。

交互式类型的题目怎么本地测试

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例及测评库下载