Lähetit

#!/usr/bin/env python3

# ajatellaan viistorivejä suorina, jolloin esim. 3x3-ruudukosta saadaan rivit:
#    x
#   x x
#  x x x
#   x x
#    x
#
# järjestetään rivit uudestaan laskennan yksinkertaistamiseksi
#    x
#    x
#   x x
#   x x
#  x x x

# jokaiselle näin saadulle vaaka- ja pystyriville voidaan sijoittaa max. yksi lähetti

TULOKSEN_JAKAJA = 10 ** 9 + 7
n, k = map(int, input().split())
riveja_yhteensa = 2 * n - 1

def valimuisti(f):
    muisti = {}
    def ymparoiva_funktio(*arg):
        avain = arg
        try:
            tulos = muisti[avain]
        except KeyError:
            tulos = f(*arg)
            muisti[avain] = tulos
        return tulos
    return ymparoiva_funktio

@valimuisti
def mahdollisuuksia(rivi, lahetteja_jaljella, parittomilla, parillisilla):
    if lahetteja_jaljella == 0:
        # kaikki asetettu, ratkaisu siis löytyi
        return 1
    if rivi > riveja_yhteensa:
        # lähettejä jäi asettamatta, ei ratkaisua
        return 0

    ruutuja = (rivi + 1) // 2
    mahd = 0

    if ruutuja % 2:
        # ollaan parittomalla rivillä
        if ruutuja > parittomilla:
            # vielä on ruutuja jäljellä, asetetaan lähetti sille
            mahd += (ruutuja - parittomilla) * mahdollisuuksia(rivi + 1, lahetteja_jaljella - 1, parittomilla + 1, parillisilla)
        # ei aseteta -laskuhaara
        mahd += mahdollisuuksia(rivi + 1, lahetteja_jaljella, parittomilla, parillisilla)
    else:
        # ollaan parillisella rivillä
        if ruutuja > parillisilla:
            # lähetti sopii, siis asetetaan
            mahd += (ruutuja - parillisilla) * mahdollisuuksia(rivi + 1, lahetteja_jaljella - 1, parittomilla, parillisilla + 1)
        # ei aseteta -laskuhaara
        mahd += mahdollisuuksia(rivi + 1, lahetteja_jaljella, parittomilla, parillisilla)

    return mahd


# import cProfile
# cProfile.run('print(mahdollisuuksia(k, 1, tuple()))')
print(mahdollisuuksia(1, k, 0, 0) % TULOKSEN_JAKAJA)

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED