Solution:
I solve this problem with DP. Even after I did it, I found that there should be some mathematical properties. But anyway, we can use DP to solve this problem.
Generally, Get the total number of almost sorted permutations of length $l$ by DP. And continuously split $n$ and $k$ into sub-DPs.
1. Conclusion: change from back to front
For example, $n=6$. For $k=1$ the answer is $(1,2,3,4,5,6)$. For $k=2$ the answer is $(1,2,3,4,6,5)$。
Based on this obvious example, we immediately get an obvious conclusion: it must be changed from the back to the front.
2. Conclusion: It must be a number of continuous and disjoint segments directly inverted
First of all, it's possible to invert some of the segments. Now the question is why it must be that. (For example after inverted $[3,5]$ for $n=6$ is $(1,2,5,4,3,6)$)
Let's try to put some number $x$ to some position $i$. So $a_i=x$. Now only two options for $a_{i-1}$: one is $a_{i-1}=x+1$, another one is $a_{i-1}<x$.
For $a_{i-1}=x+1$. Now the thing is we are trying to put $x+1$ to $i-1$. Then same problem for $i-2$. And keep choosing the first option. Then we found that we are inverting the segment.
For $a_{i-1}<x$. If so, then for any $j<i$, we have $a_j<a_i$. Because if $a_j>a_i$, then there is only one way to get it. The way is choosing option 1 for $x$.
Finally, obviously, two disjoint segments can be inverted. For example, $(3,2,1,4,6,5)$, the inversion of $[1,3]$ has nothing to do with the inversion of $[5,6]$.
So just give a full example. if $n=6$. if we invert number 3 and number 4. Then we get $(1,2,4,3,5,6)$. But if we want to include number 1 and number 2 in the inversion. Then only way is $(4,3,2,1,5,6)$.
3. Get the total number of almost sorted permutations of length $n$ (preprocess)
Let $dp[i][0]$ represent the number of almost sorted permutations with of length $i$. Whether it’s inverted from the first number or not. For example $(1,3,2)$ will be count in $dp[2][0], dp[3][0],...$.
Let $dp[i][1]$ represent the number of almost sorted permutations with of length $i$. Which is inverted from the first number. For example $(1,3,2)$ will not be count in dp[3][0]$.
So we have $dp[i][1]=1+\sum_{j=1}^{i-2}dp[j][0]$ and $dp[i][0]=dp[i][1]+dp[i-1][0]$。
Which means $dp[i][1]$ is equal to the sum of:
- After inverted the segment which start $i$ and the length is $i-j$. The total number of almost sorted permutations of The remain part (segment with length $j$). And the number is $dp[j][0]$.
- Plus 1 for the case: invert the segment from $i$ to $n$.
The $dp[i][0]$ is equal to the sum of the $dp[i][1]$ and $dp[i-1][0]$.
For example:
Consider $dp[5][1]$. There are 4 case: $(2,1,?,?,?)$, $(3,2,1,?,?)$, $(4,3,2,1,?)$ and $(5,4,3,2,1)$. So when $i=5$, the maximum of $j$ is $i-2=3$, so there are three ?s. And the number of almost sorted permutations of these three ?s is $dp[3][0]$。
So $dp[5][1]=dp[3][0]+dp[2][0]+dp[1][0]+1$。
And I found that: $dp[i][0]=2^{i-1}$，$dp[i][1]=2^{i-2}$. Not sure why.
4. Find out the first invert position for current $n$ and $k$.
First of all, base on the Conclusion #2. So We hope that the length of the first inversion is as small as possible. For example if can invert $[3,4]$ first for $(1,2,3,4,5,6)$, will not invert $[3,5]$. Because $(1,2,4,3,5,6)$ is smaller than $(1,2,5,4,3,6)$。
So we can use $dp[i][0]$ to find out the first invert position for current $n$ and $k$. That is the minimum $i$ which can make $dp[i][0]\geq{k}$. And so that the $n-i+1$ is first invert position.
And then, we enumerate the length of inversion: $l$. wihch make $dp[i-1][0]+\sum_{j=i-l}^{1}dp[j][0]\geq{k}$.
So the problem become that: For the permutations which length is $i-l$, we want to find the $k-dp[i-1][0]-\sum_{j=i-l+1}^{1}dp[j][0]$-th almost sorted permutations. (Please note that here is $i-(l-1)$. Because the $l$ we found is the first length can make the sum bigger than $k$.)
Code:
