## 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]$ 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, dp,...$.

## Code: 蜀ICP备19018968号