题目背景

下发文件来源 QOJ。

仅支持 C++ 交互，请使用 C++17 或者更高语言版本提交。

你不需要引入头文件，但请在代码头部加入如下内容：

extern "C"
{
	int valid(int n, int inputSeq[]);
	int replacement(int n, int gondolaSeq[], int replacementSeq[]);
	int countReplacement(int n, int inputSeq[]);
}

题目描述

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

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

你喜欢去缆车站上观察缆车过站。一个 缆车序列（gondola sequence） 是由缆车过站次序形成的 $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$	$6$	$(4,5,6,2,3)$
$4$	$7$	$(6,2,3,7,5)$
$7$	$8$	$(3,8,5,6,2)$

一个 替换序列（replacement sequence） 是一个由故障缆车编号组成的序列，其次序与故障发生次序相同。在前面的例子中，替换序列是 $(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

子任务	分值	$n$	$inputSeq$
$1$	$5$	$n\le 100$	从 $1$ 到 $n$ 的数字恰好各出现一次
$2$		$n\le 100,000$	$1\le inputSeq\le n$
$3$	$10$		$1\le inputSeq\le 250,000$

例子

子任务	$inputSeq$	返回值	备注
$1$	$(1,2,3,4,5,6,7)$	$1$
	$(3,4,5,6,1,2)$
	$(1,5,3,4,2,7,6)$	$0$	$1$ 不能恰好出现在 $5$ 之前
	$(4,3,2,1)$		$4$ 不能恰好出现在 $3$ 之前
$2$	$(1,2,3,4,5,6,5)$		有两个缆车编号都是 $5$
$3$	$(2,3,4,9,6,7,1)$	$1$	替换序列是 $(5,8)$
	$(10,4,3,11,12)$	$0$	$4$ 不能恰好出现在 $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

子任务	分值	$n$	$gondolaSeq$
$4$	$5$	$n\le 100$	$1\le gondolaSeq[i]\le n+1$
$5$	$10$	$n\le 1,000$	$1\le gondolaSeq[i]\le 5,000$
$6$	$20$	$n\le 100,000$	$1\le gondolaSeq[i]\le 250,000$

例子

子任务	$gondolaSeq$	返回值	$replacementSeq$
$4$	$(3,1,4)$	$1$	$(2)$
	$(5,1,2,3,4)$	$0$	$()$
$5$	$(2,3,4,9,6,7,1)$	$2$	$(5,8)$

替换序列计数

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

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

子任务 7、8、9、10

子任务	分值	$n$	$inputSeq$
$7$	$5$	$4\le n\le 50$	$1\le inputSeq[i]\le n+3$
$8$	$15$		$1\le inputSeq[i]\le 100$，初始缆车 $1,\dots,n$ 中至少有 $n-3$ 个不会发生故障。
$9$		${n\le 100,000}$	$1\le inputSeq[i]\le 250,000$
$10$		$n\le 100,000$	$1\le inputSeq[i]\le 1,000,000,000$

例子

子任务	$inputSeq$	返回值	替换序列
$7$	$(1,2,7,6)$	$2$	$(3,4,5)$ 或 $(4,5,3)$
$8$	$(2,3,4,12,6,7,1)$	$1$	$(5,8,9,10,11)$
$9$	$(4,7,4,7)$	$0$	$inputSeq$ 不是一个缆车序列
$10$	$(3,4)$	$2$	$(1,2)$ 或 $(2,1)$

实现细节

本题只支持 C/C++。

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

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$，此行包含 $gondolaSeq[0],\dots,gondolaSeq[n-1]$。否则此行包含 $inputSeq[0],\dots,inputSeq[n-1]$。

见下发文件

见下发文件