Keygen 3

We need print exactly $\min(k,2000)$ valid permutations. The annoying part is not checking one permutation. The annoying part is knowing when there are fewer than $2000$ and not missing any. So we need a way to split the world into a small exact case and a big guaranteed-$2000$ case.

The clean trick is to stop looking at bitonic permutations directly.

Anti-bitonic instead

Call a permutation anti-bitonic if it first decreases and then increases. Since all values are distinct, its minimum is $1$, so every anti-bitonic permutation has the form:

$$\text{some subset of }\{2,\ldots,n\}\text{ in decreasing order},\quad 1,\quad\text{the rest in increasing order}.$$

There are still exactly $2^{n-1}$ of them.

Now define

$$q_i = n+1-p_{n+1-i}.$$

This reverses positions and complements values. It turns anti-bitonic permutations into bitonic permutations. More importantly, it preserves cycle count, because it is just relabeling indices by $i\mapsto n+1-i$. So we can generate anti-bitonic permutations, then convert them at the end.

Good. One headache gone.

Cycles and fixed points

Let the target number of cycles be $m$, and define the cycle deficit

$$d=n-m.$$

A fixed point contributes $1$ cycle using $1$ element, so it contributes nothing to $d$. A non-trivial cycle of length $\ell\ge 2$ contributes $1$ cycle using $\ell$ elements, so it contributes

$$\ell-1$$

to $d$.

Therefore, if there are $s$ non-fixed elements, then

$$d \ge \frac{s}{2},$$

because every non-trivial cycle has length at least $2$. Equivalently,

$$s\le 2d.$$

So when $d\le 9$, there are at most $18$ non-fixed elements, meaning at least $n-18$ fixed points.

Now look at an anti-bitonic permutation whose first value is $x$.

Every value greater than $x$ is fixed. Why? Since $x$ is the maximum value placed on the decreasing left side, all values $x+1,x+2,\ldots,n$ are on the increasing right side. For any such value $y$, all values smaller than $y$ appear before it, so it lands exactly at position $y$.

Among values $1,2,\ldots,x$, there is at most one fixed point. On the decreasing side the possible fixed-point condition can happen at most once, because one side of the equality moves down while the other moves up. On the increasing side below $x$, positions are shifted to the right by selected larger values, so they are not fixed.

So the total number of fixed points is at most

$$(n-x)+1.$$

If $d\le 9$, we need at least $n-18$ fixed points, so

$$n-x+1\ge n-18,$$

which gives

$$x\le 19.$$

That is the exact-small case: if $d\le 9$, every valid anti-bitonic permutation has first value at most $19$. We can brute force all of those. The count is only

$$1+\sum_{x=2}^{19}2^{x-2}=2^{18},$$

which is tiny. For each candidate, compute the cycle count directly and keep the ones with $m$ cycles. This enumerates all valid permutations in this case, so the output count is exact. No funny business.

The large-deficit case

Now suppose

$$d=n-m\ge 10.$$

Here the answer is always at least $2000$, and we only need construct $2000$ examples.

We use length $18$ as a seed size. Brute force all anti-bitonic permutations of length $18$. For every cycle count

$$c\in[1,8],$$

there are at least $2000$ such permutations. This is a constant-size fact verified by the same exhaustive generation: there are only $2^{17}$ candidates, so this is not expensive or sketchy.

Now we need grow a seed permutation while controlling the cycle count.

There are two operations on an anti-bitonic permutation $p$ of length $N$.

Operation A: add one cycle.

Append $N+1$ to the end:

$$p\to [p_1,p_2,\ldots,p_N,N+1].$$

This keeps the permutation anti-bitonic and adds a new fixed point, so the number of cycles increases by $1$.

Operation B: keep the same number of cycles.

Append $N+1$, then let $x=p_1$ and swap positions $1$ and $x+1$.

In an anti-bitonic permutation, position $x+1$ contains value $x+1$, so it is a fixed point. After appending, we have one new fixed point. Swapping positions $1$ and $x+1$ inserts that fixed point into the cycle containing $1$, decreasing the cycle count by $1$. Net effect:

$$+1-1=0.$$

The permutation stays anti-bitonic: the first value increases from $x$ to $x+1$, and the value $x$ moves into exactly the spot where it belongs.

So Operation A changes $(N,C)$ into $(N+1,C+1)$, while Operation B changes it into $(N+1,C)$.

For target $(n,m)$ with $d=n-m\ge 10$, choose a seed cycle count

$$c=\max(1,18-d).$$

Then the seed deficit is

$$d_0=18-c\le d.$$

Use Operation B exactly $d-d_0$ times, increasing the deficit until it matches $d$. Use Operation A for all remaining growth steps. The final length becomes $n$, and the final cycle count becomes $m$.

Since we start from $2000$ distinct seeds and both operations are injective, we get $2000$ distinct valid anti-bitonic permutations. Convert each one to bitonic and print it.

Complexity

Everything is bounded by brute force over at most $2^{18}$ candidates, each checked in $O(n)$. The output size is at most $2000\cdot 100$, so this easily fits.

The whole solution is basically: brute force when the math proves brute force is complete; otherwise use constant seeds and grow them. Very 3200-looking, but the final code is honestly pretty tame.