### IOI '14 - Taipei, Taiwan

## Gondola

Mao-Kong Gondola is a famous attraction in Taipei. The gondola system consists of a circular rail, a single station, and `n` gondolas numbered consecutively from 1 to `n` running around the rail in a fixed direction. After gondola `i` passes the station, the next gondola to pass the station will be gondola `i` + 1 if `i` < `n`, or gondola 1 if `i` = `n`.

Gondolas may break down. Luckily we have an infinite supply of spare gondolas, which are numbered `n` + 1, `n` + 2, and so on. When a gondola breaks down we replace it (in the same position on the track) with the first available spare gondola, that is, the one with the lowest number. For example, if there are five gondolas and gondola 1 breaks down, then we will replace it with gondola 6.

You like to stand at the station and watch the gondolas as they pass by. A *gondola sequence* is a sequence of `n` numbers of gondolas that pass the station. It is possible that one or more gondolas broke down (and were replaced) before you arrived, but none of the gondolas break down while you are watching.

Note that the same configuration of gondolas on the rail can give multiple gondola sequences, depending on which gondola passes first when you arrive at the station. For example, if none of the gondolas have broken down then both (2, 3, 4, 5, 1) and (4, 5, 1, 2, 3) are possible gondola sequences, but (4, 3, 2, 5, 1) is not (because the gondolas appear in the wrong order).

If gondola 1 breaks down, then we might now observe the gondola sequence (4, 5, 6, 2, 3). If gondola 4 breaks down next, we replace it with gondola 7 and we might observe the gondola sequence (6, 2, 3, 7, 5). If gondola 7 breaks down after this, we replace it with gondola 8 and we may now observe the gondola sequence (3, 8, 5, 6, 2).

broken gondola | new gondola | possible gondola sequence |
---|---|---|

1 | 6 | (4, 5, 6, 2, 3) |

4 | 7 | (6, 2, 3, 7, 5) |

7 | 8 | (3, 8, 5, 6, 2) |

A *replacement sequence* is a sequence consisting of the numbers of the gondolas that have broken down, in the order in which they break down. In the previous example the replacement sequence is (1, 4, 7). A replacement sequence `r` *produces* a gondola sequence `g` if, after gondolas break down according to the replacement sequence `r`, the gondola sequence `g` may be observed.

### Gondola Sequence Checking

In the first three subtasks you must check whether an input sequence is a gondola sequence. See the table below for examples of sequences that are and are not gondola sequences. You need to implement an operation `valid`

.

`valid(n, inputSeq)`

`n`

: the length of the input sequence`inputSeq`

: array of length`n`;`inputSeq[i]`

is element`i`of the input sequence, for 0 ≤`i`≤`n`− 1.- For this operation you should output 1 if the input sequence is a gondola sequence, or 0 otherwise.

#### Subtasks 1, 2, 3

subtask | % of points | n | `inputSeq` |
---|---|---|---|

1 | 5 | n ≤ 100 | has each number from 1 to n exactly once |

2 | 5 | n ≤ 100,000 | 1 ≤ `inputSeq[i]` ≤ n |

3 | 10 | n ≤ 100,000 | 1 ≤ `inputSeq[i]` ≤ 250,000 |

#### Examples

subtask | `inputSeq` | output | note |
---|---|---|---|

1 | (1, 2, 3, 4, 5, 6, 7) | 1 | |

1 | (3, 4, 5, 6, 1, 2) | 1 | |

1 | (1, 5, 3, 4, 2, 7, 6) | 0 | 1 cannot appear just before 5 |

1 | (4, 3, 2, 1) | 0 | 4 cannot appear just before 3 |

2 | (1, 2, 3, 4, 5, 6, 5) | 0 | two gondolas numbered 5 |

3 | (2, 3, 4, 9, 6, 7, 1) | 1 | replacement sequence (5, 8) |

3 | (10, 4, 3, 11, 12) | 0 | 4 cannot appear just before 3 |

### Replacement Sequence

In the next three subtasks you must construct a possible replacement sequence that produces a given gondola sequence. Any such replacement sequence will be accepted. You need to implement an operation `replacement`

.

`replacement(n, gondolaSeq, replacementSeq)`

`n`

is the length of the input sequence`gondolaSeq`

: array of length`n`;`gondolaSeq`

is guaranteed to be a gondola sequence, and`gondolaSeq[i]`

is element`i`of the sequence, for 0 ≤`i`≤`n`− 1.- For this operation you should output
`l`, the length of the replacement sequence, followed by`l`integers representing the replacement sequence.

#### Subtasks 4, 5, 6

subtask | % of points | n | `gondolaSeq` |
---|---|---|---|

4 | 5 | n ≤ 100 | 1 ≤ `gondolaSeq[i]` ≤ n + 1 |

5 | 10 | n ≤ 1,000 | 1 ≤ `gondolaSeq[i]` ≤ 5,000 |

6 | 20 | n ≤ 100,000 | 1 ≤ `gondolaSeq[i]` ≤ 250,000 |

#### Examples

subtask | `gondolaSeq` | output | `replacementSeq` |
---|---|---|---|

4 | (3, 1, 4) | 1 2 | (2) |

4 | (5, 1, 2, 3, 4) | 0 | ( ) |

5 | (2, 3, 4, 9, 6, 7, 1) | 2 5 8 | (5, 8) |

### Count Replacement Sequences

In the next four subtasks you must count the number of possible replacement sequences that produce a given sequence (which may or may not be a gondola sequence), modulo **1,000,000,009**. You need to implement an operation `countReplacement`

.

`countReplacement(n, inputSeq)`

`n`

: the length of the input sequence`inputSeq`

: array of length`n`;`inputSeq[i]`

is element`i`of the input sequence, for 0 ≤`i`≤`n`− 1.- If the input sequence is a gondola sequence, then count the number of replacement sequences that produce this gondola sequence (which could be extremely large),
*and output this number modulo*. If the input sequence is not a gondola sequence, then output 0. If the input sequence is a gondola sequence but no gondolas broke down, then output 1.**1,000,000,009**

#### Subtasks 7, 8, 9, 10

subtask | % of points | n | `inputSeq` |
---|---|---|---|

7 | 5 | 4 ≤ n ≤ 50 | 1 ≤ `inputSeq[i]` ≤ n + 3 |

8 | 15 | 4 ≤ n ≤ 50 | 1 ≤ `inputSeq[i]` ≤ 100, and at least n − 3 of the initialgondolas 1, …, n did not break down. |

9 | 15 | n ≤ 100,000 | 1 ≤ `inputSeq[i]` ≤ 250,000 |

10 | 10 | n ≤ 100,000 | 1 ≤ `inputSeq[i]` ≤ 1,000,000,000 |

#### Examples

subtask | `inputSeq` | output | replacement sequence |
---|---|---|---|

7 | (1, 2, 7, 6) | 2 | (3, 4, 5) or (4, 5, 3) |

8 | (2, 3, 4, 12, 6, 7, 1) | 1 | (5, 8, 9, 10, 11) |

9 | (4, 7, 4, 7) | 0 | `inputSeq` is not a gondola sequence |

10 | (3, 4) | 2 | (1, 2) or (2, 1) |

### Input Format

Line 1: `T`, the subtask number your program must solve (1 ≤ `T` ≤ 10).

Line 2: `n`, the length of the input sequence.

Line 3: If `T` is 4, 5, or 6, this line contains `gondolaSeq[0]`

, …, `gondolaSeq[`

. Otherwise this line contains `n`-1]`inputSeq[0]`

, …, `inputSeq[`

.`n`-1]

### Output Format

If `T` is 1, 2, or 3: the output should consist of a single integer, 1 if the input sequence is a gondola sequence, or 0 otherwise.

If `T` is 4, 5, or 6: the output should consist of the integer `l`, the length of the replacement sequence, followed by `l` integers on the same line representing the replacement sequence itself.

If `T` is 7, 8, 9, or 10: the only line of output should consist of a single integer, the number of replacement sequences producing the input sequence modulo 1,000,000,009 if the input sequence is a gondola sequence, 0 if the input sequence is not a gondola sequence, or 1 if the input sequence is a gondola sequence but no gondolas broke down.

### Examples

## Sample Input 11 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 ## Sample Output 10 |
|||

## Sample Input 22 6 3 4 5 6 1 2 ## Sample Output 21 |
## Sample Input 33 7 1 2 3 4 5 6 5 ## Sample Output 30 |
## Sample Input 44 2 3 2 ## Sample Output 41 1 |
## Sample Input 55 14 12 13 14 1 2 3 4 5 6 7 8 9 10 11 ## Sample Output 50 |

## Sample Input 66 50 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 51 47 48 49 50 1 2 3 ## Sample Output 61 46 |
|||

## Sample Input 77 11 4 5 6 7 8 9 10 11 1 2 3 ## Sample Output 71 |
## Sample Input 88 14 6 94 8 9 10 93 12 13 95 1 2 3 4 5 ## Sample Output 8224280120 |
## Sample Input 99 4 1 2 7 6 ## Sample Output 92 |
## Sample Input 1010 4 4 7 4 7 ## Sample Output 100 |

All Submissions

Best Solutions

**Point Value:** 20 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 256M

**Added:** Jul 29, 2014

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

Cassian_gon Jul 16, 2016 - 1:51:45 pm UTCif (pos[i] < 1 || pos[i] > n)

{

cout << ' ' << pos[i] - 1 << ':';

return 12;

}

if (gondolaSeq[pos[i] - 1] < 0)

{

cout << ' ' << n << ' ' << pos[i] - 1 << '?' << gondolaSeq[pos[i] - 1];

return 11;

}

So something that writes random stuff to stdout in cases that should never happen. Now I get AC

spencereiron Mar 27, 2016 - 11:57:54 pm UTC Speeding up exponentiationpyrexshortson Mar 28, 2016 - 10:38:59 pm UTC Re: Speeding up exponentiationAlso make sure you are using fast exponentiation in log k time.

spencereiron Mar 28, 2016 - 11:47:25 pm UTC Re: Speeding up exponentiationbahosain889on Jul 20, 2015 - 10:32:18 pm UTC Subtask 1,2,31 4

1 7 4 9

ans is 0

FatalEagleon Jul 20, 2015 - 10:56:51 pm UTC Re: Subtask 1,2,3AlanMon Jun 07, 2015 - 7:48:17 pm UTC Wrong test datadopa0509on Aug 10, 2014 - 5:54:28 pm UTC (Subtask 4, 5, 6)'s Special Judge is doubtful...So I downloaded the data from the official website and tested.

When I built a sequence as my program printed, I got the same sequence with input data. And this is correct.

Please, confirm this out.

Alexon Aug 10, 2014 - 6:50:10 pm UTC Re: (Subtask 4, 5, 6)'s Special Judge is doubtful...dopa0509on Aug 13, 2014 - 7:03:12 am UTC Re: (Subtask 4, 5, 6)'s Special Judge is doubtful...bbi5291on Aug 13, 2014 - 8:13:33 am UTC Re: (Subtask 4, 5, 6)'s Special Judge is doubtful...dopa0509on Aug 13, 2014 - 1:00:37 pm UTC Re: (Subtask 4, 5, 6)'s Special Judge is doubtful...dopa0509on Aug 18, 2014 - 8:24:34 am UTC Re: (Subtask 4, 5, 6)'s Special Judge is doubtful...Alexon Aug 19, 2014 - 4:45:54 am UTC Re: (Subtask 4, 5, 6)'s Special Judge is doubtful...Note: The length of your replacement sequences should not exceed 250000, or they will be graded as WA.

dopa0509on Aug 19, 2014 - 10:59:48 am UTC Re: (Subtask 4, 5, 6)'s Special Judge is doubtful...