Hi Codeforces community,↵
↵
Recently I have come across a problem which turned out to be tough for me. I hope that I can get some help from you.↵
Problem Statement↵
-----------------↵
A permutation $A$ of first $N$ integers from $1$ to $N$ is good if it has exactly $K$ good positions. A position $i$ is good only if $abs(A[i]-i)=1$. The task is to count how many permutation of first $N$ integers like that, modulo $10^9+7$.↵
### Input↵
$N$ and $K$, $1 \leq N \leq 1000 , 0 \leq K \leq N$↵
### Output↵
Number of permutation of first $N$ integers from $1$ to $N$ that has exactly $K$ good positions, modulo $10^9+7$↵
↵
#### Example↵
For $N=3, K=2$, there are $4$ permutations that has $2$ good positions. They are $(1, 3, 2)$ , $(2, 1, 3)$ , $(2, 3, 1)$ , $(3, 1, 2)$.↵
↵
You may want to submit your solution here (written in Vietnamese, required SPOJ account): [http://www.spoj.com/PTIT/problems/P172PROI/](http://www.spoj.com/PTIT/problems/P172PROI/)↵
↵
I think it is a DP problem although I could not come up with a solution or any idea. Any help will be appreciated.↵
↵
Thanks in advance.
↵
Recently I have come across a problem which turned out to be tough for me. I hope that I can get some help from you.↵
Problem Statement↵
-----------------↵
A permutation $A$ of first $N$ integers from $1$ to $N$ is good if it has exactly $K$ good positions. A position $i$ is good only if $abs(A[i]-i)=1$. The task is to count how many permutation of first $N$ integers like that, modulo $10^9+7$.↵
### Input↵
$N$ and $K$, $1 \leq N \leq 1000 , 0 \leq K \leq N$↵
### Output↵
Number of permutation of first $N$ integers from $1$ to $N$ that has exactly $K$ good positions, modulo $10^9+7$↵
↵
#### Example↵
For $N=3, K=2$, there are $4$ permutations that has $2$ good positions. They are $(1, 3, 2)$ , $(2, 1, 3)$ , $(2, 3, 1)$ , $(3, 1, 2)$.↵
↵
You may want to submit your solution here (written in Vietnamese, required SPOJ account): [http://www.spoj.com/PTIT/problems/P172PROI/](http://www.spoj.com/PTIT/problems/P172PROI/)↵
↵
I think it is a DP problem although I could not come up with a solution or any idea. Any help will be appreciated.↵
↵
Thanks in advance.
