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

tulosmuisti = {}

def mahdollisuuksia(rivi, lahetteja_jaljella, parittomilla, parillisilla):
    avain = (rivi, lahetteja_jaljella, parittomilla, parillisilla)
    try:
        return tulosmuisti[avain]
    except KeyError:
        pass

    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)
    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 lähettiä -laskuhaara
    mahd += mahdollisuuksia(rivi + 1, lahetteja_jaljella, parittomilla, parillisilla)

    tulos = mahd % TULOKSEN_JAKAJA
    tulosmuisti[avain] = tulos
    return tulos

# import time
# alku = time.time()
print(mahdollisuuksia(1, k, 0, 0) % TULOKSEN_JAKAJA)
# print(time.time() - alku)

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: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED