Problem:


Score : 600 points

Problem Statement

Let us define the oddness of a permutation p = {p_1,\ p_2,\ ...,\ p_n} of {1,\ 2,\ ...,\ n} as \sum_{i = 1}^n |i - p_i|.

Find the number of permutations of {1,\ 2,\ ...,\ n} of oddness k, modulo 10^9+7.

Constraints

All values in input are integers.

1 \leq n \leq 50

0 \leq k \leq n^2

Input

Input is given from Standard Input in the following format:

n k

Output

Print the number of permutations of {1,\ 2,\ ...,\ n} of oddness k, modulo 10^9+7.

Sample Input 1

3 2

Sample Output 1

2

There are six permutations of {1,\ 2,\ 3}. Among them, two have oddness of 2:  {2,\ 1,\ 3} and {1,\ 3,\ 2}.

Sample Input 2

39 14

Sample Output 2

74764168



Sample input:
3 2


Sample output:
2

Submission status: Accepted

Solution code:
import sys

MOD = 10**9 + 7

N, K = map(int, input().split())

maxS = N*N//2
if K > maxS or K%2:
    print(0)
    sys.exit()

dp = [[0]*(maxS+1) for j in range(N+1)]
dp[0][0] = 1
for i in range(1, N+1):
    dp2 = [[0]*(maxS+1) for j in range(N+1)]
    for j in range(i+1):
        for s in range(0, maxS+1, 2):
            s0 = s-2*j
            if s0 < 0: continue
            dp2[j][s] = (2*j+1)*dp[j][s0]
            if j+1 <= N:
                dp2[j][s] += (j+1)*(j+1)*dp[j+1][s0]
            if j-1 >= 0:
                dp2[j][s] += dp[j-1][s0]
            dp2[j][s] %= MOD
    dp = dp2

print(dp[0][K])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
MOD = 10 ** 9 + 7
dp = [[[0] * 2600 for i in range(N + 5)] for j in range(N + 5)]
dp[0][0][0] = 1

for i in range(N):
    for j in range(N + 1):
        for k in range(K + 1):
            if dp[i][j][k] == 0:
                continue
            a = k + 2 * j
            dp[i + 1][j][a] += dp[i][j][k]
            dp[i + 1][j][a] += dp[i][j][k] * j
            if j > 0:
                dp[i + 1][j - 1][a] += dp[i][j][k] * j * j
            dp[i + 1][j][a] += dp[i][j][k] * j
            dp[i + 1][j + 1][a] += dp[i][j][k]
            dp[i + 1][j][a] %= MOD
            dp[i + 1][j - 1][a] %= MOD
            dp[i + 1][j + 1][a] %= MOD

print(dp[N][0][K])