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: Runtime Error

Solution code:
import numpy as np

N, K = map(int,input().split())
MOD = 10**9+7

# dp[i][j][k]:
# ウサギ1~i, カメ1~i (うちj個は相手が未定)まで見ていて，
# 確定している奇妙さがkであるような場合の数
dp = np.zeros((55,55,55), dtype='int64')
dp[0][0][0] = 1

for i in range(N+1):
    for j in range(N+1):
        for k in range(N+1):
            if k-2*j < 0 or i <= 0: continue

            dp[i][j][k] += (2*j+1) * dp[i-1][j][k-2*j] % MOD
            dp[i][j][k] %= MOD

            dp[i][j][k] += (j+1)*(j+1)*dp[i-1][j+1][k-2*j] % MOD
            dp[i][j][k] %= MOD

            if j > 0:
                dp[i][j][k] += dp[i-1][j-1][k-2*j]
                dp[i][j][k] %= MOD
            
print(dp[N][0][K])

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, K = read_values()
    dp = [
        [[0 for i in range(N ** 2 + 1)] for ii in range(N + 1)] for iii in range(N + 1)
    ]
    dp[0][0][0] = 1

    for i in range(1, N + 1):
        for j in range(N + 1):
            for k in range(K + 1):
                if k - 2 * j < 0:
                    continue

                dp[i][j][k] = (
                    (2 * j + 1) * dp[i - 1][j][k - 2 * j]
                    + (j + 1) * (j + 1) * dp[i - 1][j + 1][k - 2 * j]
                    + dp[i - 1][j - 1][k - 2 * j]
                ) % mod

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import copy
n,m=map(int,input().split())
a=[[0 for _ in range(m+2)] for _ in range(n+2)]
a[0][0]=1
a[1][2]=1
for i in range(1,n):
  b=copy.deepcopy(a)
  for j in range(0,i+2):
    for k in range(0,m+1):
      if k>=2*j:
        a[j][k]=(2*j+1)*b[j][k-2*j]+(j+1)**2*b[j+1][k-2*j]
        if j>0:
          a[j][k]+=b[j-1][k-2*j]
      else:
        a[j][k]=0
print(a[0][m]%(10**9+7))

Submission status: Runtime Error

Solution code:

mod = 10 ** 9 + 7

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

dp = [[[0 for _ in range(2510)] for _ in range(51)] for _ in range(51)]
dp[0][0][0] = 1

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

            dp[i + 1][j][k + 2 * j] += dp[i][j][k]

            if j > 0:
                dp[i + 1][j - 1][k + 2 * j - 2] += dp[i][j][k] * j * j


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

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

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

dp = [[[0 for _ in range(2510)] for _ in range(51)] for _ in range(51)]
dp[0][0][0] = 1

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

            dp[i + 1][j][k + 2 * j] += dp[i][j][k]

            if j > 0:
                dp[i + 1][j - 1][k + 2 * j - 2] += dp[i][j][k] * j * j


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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,K=map(int,input().split())
    dp=[[[0]*2600 for _ in range(55)] for _ in range(55)]
    dp[0][0][0]=1
    for i in range(n):
        for j in range(n):
            for k in range(K+1):
                dp[i+1][j][k+2*j]+=(2*j+1)*dp[i][j][k]
                dp[i+1][j][k+2*j]%=MOD
                dp[i+1][j+1][k+2*(j+1)]+=dp[i][j][k]
                dp[i+1][j+1][k+2*(j+1)]%=MOD
                if(j>0):
                    dp[i+1][j-1][k+2*(j-1)]+=j*j*dp[i][j][k]
                    dp[i+1][j-1][k+2*(j-1)]%=MOD
    print(dp[n][0][K])
resolve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,K=map(int,input().split())
    dp=[[[0]*2600 for _ in range(55)] for _ in range(55)]
    dp[0][0][0]=1
    for i in range(n):
        for j in range(n):
            for k in range(K+1):
                dp[i+1][j][k+2*j]+=(2*j+1)*dp[i][j][k]
                dp[i+1][j][k+2*j]%=MOD
                dp[i+1][j+1][k+2*(j+1)]+=dp[i][j][k]
                dp[i+1][j+1][k+2*(j+1)]%=MOD
                dp[i+1][j-1][k+2*(j-1)]+=j*j*dp[i][j][k]
                dp[i+1][j-1][k+2*(j-1)]%=MOD
    print(dp[n][0][K])
resolve()

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, k = LI()
dp = [[[0]*n**2*3 for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(i+1):
        for l in range(k+1):
            dp[i+1][j+1][l+2*(j+1)] += dp[i][j][l]
            dp[i+1][j+1][l+2*(j+1)]%=mod
            dp[i+1][j][l+2*j] += dp[i][j][l]*(j*2+1)
            dp[i+1][j][l+2 * j] %= mod
            if j != 0:
                dp[i+1][j-1][l+(j-1)*2] += dp[i][j][l]*j*j
                dp[i+1][j-1][l+(j-1)*2]%=mod



print(dp[n][0][k]%mod)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, k = LI()
dp = [[[0]*n*(n+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(i+1):
        for l in range(k+1):
            dp[i+1][j+1][l+2*(j+1)] += dp[i][j][l]
            dp[i+1][j+1][l+2*(j+1)]%=mod
            dp[i+1][j][l+2*j] += dp[i][j][l]*(j*2+1)
            dp[i+1][j][l+2 * j] %= mod
            if j != 0:
                dp[i+1][j-1][l+(j-1)*2] += dp[i][j][l]*j*j
                dp[i + 1][j - 1][l + (j - 1) * 2]%=mod



print(dp[n][0][k]%mod)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, k = LI()
dp = [[[0] * (n * (n + 1)) for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(i+1):
        for l in range(k + 1):
            dp[i+1][j+1][l+2*(j+1)] += dp[i][j][l]
            dp[i + 1][j + 1][l + 2 * (j + 1)]%=mod
            dp[i+1][j][l+2*j] += dp[i][j][l]*(j*2+1)
            dp[i + 1][j][l + 2 * j] %= mod
            if j != 0:
                dp[i+1][j-1][l+(j-1)*2] += dp[i][j][l]*j*j
                dp[i + 1][j - 1][l + (j - 1) * 2]%=mod


print(dp[n][0][k])

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, k = LI()
dp = [[[0] * (n * (n + 1)) for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(i+1):
        for l in range(k + 1):
            dp[i + 1][j + 1][l+2*(j + 1)] += dp[i][j][l]
            dp[i + 1][j][l+2*j] += dp[i][j][l]*(j*2+1)
            if j != 0:
                dp[i+1][j-1][l+(j-1)*2] += dp[i][j][l]*j*j


print(dp[n][0][k]%mod)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, k = LI()
dp = [[[0] * (n * (n + 1)) for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(i+1):
        for l in range(k + 1):
            dp[i + 1][j + 1][l+2*(j + 1)] += dp[i][j][l]
            dp[i + 1][j][l+2*j] += dp[i][j][l]*(j*2+1)
            if j != 0:
                dp[i+1][j-1][l+(j-1)*2] += dp[i][j][l]*j*j

print(dp)
print(dp[n][0][k]%mod)

Submission status: Runtime Error

Solution code:
# -*- coding:utf-8 -*-
# /usr/bin/python3

import numpy as np

def main():
  n, score = map(int, input().strip().split(' '))
  dp = np.zeros((51,51,(50**2)//2+60), dtype=np.int)
  dp[0,0,0] = 1
  for i in range(n):
    for j in range(0, i+1):
      for k in range(0, score+1):
        dp[i, j, k] %= (10**9+7)
        # a
        dp[i+1, j, k+j] += dp[i, j, k]
        # b
        dp[i+1, j+1, k+(j+1)] += dp[i, j, k]
        # c
        dp[i+1, j, k+j] += dp[i, j ,k] * (j*2)
        # d
        if j-1 >= 0:
          dp[i+1, j-1, k+(j-1)] += dp[i, j, k] * (j**2)
  if score % 2 == 1:
    print(0)
  else:
    print(dp[n][0][score//2] % (10**9+7))

  pass

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
# -*- coding:utf-8 -*-
# /usr/bin/python3

import numpy as np

def main():
  n, score = map(int, input().strip().split(' '))
  dp = np.zeros((51,51,(50**2)//2+1), dtype=np.int)
  dp[0,0,0] = 1
  for i in range(n):
    for j in range(0, i+1):
      for k in range(0, score+1):
        # a
        dp[i+1, j, k+j] += dp[i, j, k]
        # b
        dp[i+1, j+1, k+(j+1)] += dp[i, j, k]
        # c
        dp[i+1, j, k+j] += dp[i, j ,k] * (j*2)
        # d
        if j-1 >= 0:
          dp[i+1, j-1, k+(j-1)] += dp[i, j, k] * (j**2)
  if score % 2 == 1:
    print(0)
  else:
    print(dp[n][0][score//2] % (10**9+7))

  pass

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
# -*- coding:utf-8 -*-
# /usr/bin/python3

import numpy as np

def main():
  n, score = map(int, input().strip().split(' '))
  dp = np.zeros((51,51,50**2+1), dtype=np.int)
  dp[0,0,0] = 1
  for i in range(n):
    for j in range(0, i+1):
      for k in range(0, score+1):
        if k % 2 != 0:
            continue
        # a
        dp[i+1, j, k+j*2] += dp[i, j, k]
        # b
        dp[i+1, j+1, k+(j+1)*2] += dp[i, j, k]
        # c
        dp[i+1, j, k+j*2] += dp[i, j ,k] * (j*2)
        # d
        if j-1 >= 0:
          dp[i+1, j-1, k+(j-1)*2] += dp[i, j, k] * (j**2)
  print(dp[n][0][score])

  pass

if __name__=='__main__':
  main()