#P4365. [IOI2014]gondola缆车

[IOI2014]gondola缆车

[IOI 2014] Gondola 缆车

题目描述

猫空缆车系统有一条环形轨道和一个车站。轨道上最初有 nn 辆缆车,编号为 1,2,…,n1,2,\ldots,n。若编号 i<ni<n 的缆车经过车站,则接下来是缆车 i+1i+1;缆车 nn 之后是缆车 11。

缆车故障时,用编号最小的尚未使用过的备用缆车原地替换。备用缆车的编号依次为 n+1,n+2,…n+1,n+2,\ldots,故障缆车不会重新使用。

你到车站后,记录连续经过车站的一整圈缆车,共 nn 个编号。观察期间不发生故障;到达前可以已经发生任意次故障。这样得到的序列称为缆车序列。同一种轨道状态从不同缆车开始观察可以得到不同序列。比如 n=5n=5 时,若从未发生故障,(2,3,4,5,1)(2,3,4,5,1) 与 (4,5,1,2,3)(4,5,1,2,3) 均可出现,(4,3,2,5,1)(4,3,2,5,1) 则不能出现。

把每辆发生故障的缆车的编号按故障先后列出,得到替换序列。若依序发生这些故障之后可以观察到某个缆车序列,就称这个替换序列生成了该缆车序列。

例如 n=5n=5 时依次更换下列缆车,替换序列为 (1,4,7)(1,4,7)。

故障缆车 新缆车 一种可观察到的缆车序列
1 6 (4,5,6,2,3)(4,5,6,2,3)
4 7 (6,2,3,7,5)(6,2,3,7,5)
7 8 (3,8,5,6,2)(3,8,5,6,2)

输入格式

第一行一个整数 TT,用于指定本次输入要求完成的任务。第二行一个整数 nn。第三行 nn 个整数 a1,…,ana_1,\ldots,a_n,表示给定的序列。

输出格式

  • T=1,2,3T=1,2,3:判断给定序列是否为缆车序列。若是,输出 11;否则输出 00。
  • T=4,5,6T=4,5,6:给定序列一定是缆车序列。构造任意一个能够生成它的替换序列,输出一行:先输出长度 ℓ\ell,再依顺序输出这 ℓ\ell 个故障编号。没有故障时只输出 00。
  • T=7,8,9,10T=7,8,9,10:输出能生成给定缆车序列的替换序列数量,对 1 000 000 0091\,000\,000\,009 取模。如果给定序列不是缆车序列,则输出 00;如果合法且没有发生过故障,则输出 11。

样例

样例输入 #1

1
30
16 26 18 19 20 13 22 21 24 25 17 27 28 29 30 1 2 3 11 5 6 8 7 9 10 12 4 23 14 15

样例输出 #1

0

样例输入 #2

6
2
3 4

样例输出 #2

2 1 2

这个样例也可以输出 2 2 1。更换完成后,两种方案都可以通过选择合适的起始缆车,观察到 (3,4)(3,4)。

原赛的其他示例如下。

TT 输入序列 结果 说明
1 (1,2,3,4,5,6,7)(1,2,3,4,5,6,7) 11 初始顺序
(3,4,5,6,1,2)(3,4,5,6,1,2) 从缆车 33 开始
(1,5,3,4,2,7,6)(1,5,3,4,2,7,6) 00 缆车 11 不会紧接着到缆车 55
(4,3,2,1)(4,3,2,1) 缆车 44 不会紧接着到缆车 33
2 (1,2,3,4,5,6,5)(1,2,3,4,5,6,5) 编号 55 重复
3 (2,3,4,9,6,7,1)(2,3,4,9,6,7,1) 11 替换序列可以是 (5,8)(5,8)
(10,4,3,11,12)(10,4,3,11,12) 00 缆车 44 不会紧接着到缆车 33
4 (3,1,4)(3,1,4) 1 2 依次输出长度及故障编号
(5,1,2,3,4)(5,1,2,3,4) 0 无故障记录
5 (2,3,4,9,6,7,1)(2,3,4,9,6,7,1) 2 5 8 依次输出长度及故障编号
7 (1,2,7,6)(1,2,7,6) 22 替换序列为 (3,4,5)(3,4,5) 或 (4,5,3)(4,5,3)
8 (2,3,4,12,6,7,1)(2,3,4,12,6,7,1) 11 替换序列为 (5,8,9,10,11)(5,8,9,10,11)
9 (4,7,4,7)(4,7,4,7) 00 编号重复
10 (3,4)(3,4) 22 替换序列为 (1,2)(1,2) 或 (2,1)(2,1)

数据范围

保证 1≤T≤101\le T\le10。

TT nn 的范围 序列限制
1 1≤n≤1001\le n\le100 11 到 nn 各出现一次
2 1≤n≤100 0001\le n\le100\,000 1≤ai≤n1\le a_i\le n
3 1≤ai≤250 0001\le a_i\le250\,000
4 1≤n≤1001\le n\le100 1≤ai≤n+11\le a_i\le n+1
5 1≤n≤1 0001\le n\le1\,000 1≤ai≤5 0001\le a_i\le5\,000
6 1≤n≤100 0001\le n\le100\,000 1≤ai≤250 0001\le a_i\le250\,000
7 4≤n≤504\le n\le50 1≤ai≤n+31\le a_i\le n+3
8 1≤ai≤1001\le a_i\le100,至少有 n−3n-3 辆初始缆车没有发生故障
9 1≤n≤100 0001\le n\le100\,000 1≤ai≤250 0001\le a_i\le250\,000
10 1≤ai≤1091\le a_i\le10^9