How to solve this permutation problem?

Правка en1, от RaidenEi, 2017-11-27 12:01:48

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 109 + 7.

Input

N and K, 1 ≤ N ≤ 1000, 0 ≤ K ≤ N

Output

Number of permutation of first N integers from 1 to N that has exactly K good positions, modulo 109 + 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/

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский RaidenEi 2017-11-27 12:04:52 0 (published)
en1 Английский RaidenEi 2017-11-27 12:01:48 1130 Initial revision (saved to drafts)