First of all, sorry for being late :( I was quite depressed because of the server's chronic breakdown during the contest. Also, all the records for Round #233 was gone after the black day, so I thought not many people will be interested in the solution. I should have been more responsible for this. I really want to apologize for people who have been waiting for this editorial.

During the contest, the only one user who solved this problem was: Petr. The contest was extended by 30 minutes, and if I remember correctly, he submitted the correct solution at about 2:25. So, congratulations to him!

Now let me explain the solution. Let us start with the case when there is no hole. Given any permutation, I will prove that it takes only at most two seconds to sort it completely. Since every permutation can be decomposed into disjoint cycles (link), we only need to take care of each decomposed cycle. That is, we only need to sort a cycle of arbitrary length in two steps.

Let's make a table of 3 rows and n columns. The first row will constitute the original, unsorted permutation. For each column, the next column will form the permutation after one second. The last column will be the sorted permutation. The following depicts the case where n = 5 and the permutation is a full cycle.

2 3 4 5 1
? ? ? ? ?
1 2 3 4 5

Now we have to show that we can fill the second column properly. Let's just fill the first number in the second column randomly, say 4, and see what happens.

2 3 4 5 1
4 ? ? ? ?
1 2 3 4 5

Because 4 replaces 2 in the second column, 2 replaces 4 and we are forced to put 2 below the 4 in first column.

2 3 4 5 1
4 ? 2 ? ?
1 2 3 4 5

Likewise, 3 replaces 2 in the third column, so we should put 3 above 2 in the third column.

2 3 4 5 1
4 3 2 ? ?
1 2 3 4 5

Repeating the process will finally give a complete, valid answer.

2 3 4 5 1
4 3 2 1 5
1 2 3 4 5

Like the example above, filling the first number in the second column by any number will give a unique and valid answer. I won't prove it formally, but by experimenting with different examples you can see it indeed works :) So now we know that (i) any permutation can be sorted in 2 seconds and, additionally, (ii) if the permutation is a cycle, there are exactly n ways of doing it. Now let us see what happens if two disjoint cycles interact with each other. Try to fill the tables below and figure out what happens. First one is a disjoint union of cycles of length 4 and 5. Second one is a union of cycles of length 4 and 4.

2 3 4 5 1 7 8 9 6      2 3 4 1 6 7 8 5 
8 ? ? ? ? ? ? ? ?      8 ? ? ? ? ? ? ? 
1 2 3 4 5 6 7 8 9      1 2 3 4 5 6 7 8

By experimenting, you will see that if two disjoint cycles A and B interact (to be precise, when an element in A swaps place with another element in B), (i) the size of A and B are equal and in that case (ii) the number of ways to achieve a complete assignment for elements of A and B is exactly the size of A (or B). I won't prove it, but it can be done formally if one wishes to.

Now we have the solution when there is no hole: decompose the permutation into disjoint cycles. Assume there are exactly c_i cycles of length l_i for each i. Let a[c, l] be the number of ways to sort c cycles of length l completely. Then the answer will be , basically because only cycles of same length interact.

To sort c cycles of length l, we can pair some of the cycles to interact with each other. Then each pair and unpaired cycle will contribute multiplicative factor l to the answer. Now we can derive a recursive formula for a[c, l]. Just take a cycle C and decide if it will be paired to different cycle or not. For the first case, C contributes multiplicative factor l and we can decide on the rest of c - 1 cycles, so there are total of l·a[c - 1, l] ways. For the second case, we have c - 1 ways to pair C with the other cycle, then the pair contributes factor l and we can decide on the remaining c - 2 cycles. This contributes l·(c - 1)·a[c - 2, l]. Adding up will give us the recursive formula.

(I'm trying my best to explain the idea, but for this part i'm not quite satisfied with it. Ask or message me if you want more clear explanation)

I will write the rest of the editorial tomorrow (my English is bad so it's quite hard to write), but I hope that this draft version will be helpful to you.

• Update

It's almost been a year since I updated this editorial. I have nothing to say but that I was lazy... However, for the sake of completeness, I'll sketch up the rest of the solution.

Computing every a[c, l] can be done in reasonable time: c_l will be at most n / l and there will be total of values of a[c, l] to compute using the recursive formula above. Given a permutation, we can count the number of cycles c_l of length l for each l and compute a[c_l, l]. Since two cycles of different length cannot interact, the number of ways to sort the whole permutation will be the multiplication of a[c_l, l]'s over all l.

Finally, we have to deal with k ≤ 12 holes. The crucial observation is that with holes, the permutation decomposes into cycles and paths. Filling the holes will group the paths to disjoint cycles. Considering every 12! possible ways will give TLE. But if we note that the order of paths in a same group does not make a change in cycle's length, we can actually deploy a bitmask DP to consider all possible way to partition at most 12 paths. Just multiply some constant to each partition and sum over (I'll skip the details).