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 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 lkm(rivi, jaljella, parittomilla, parillisilla):
    '''palauta lähettien sijoitusyhdistelmien määrä
 
    rivi = käsiteltävän rivin järjestysnumero
    jaljella = sijoittamattomia lähettejä jäljellä
    parittomilla = lähettejä sijoitettu parittomille ruuduille
    parillisilla = lähettejä sijoitettu parillisille ruuduille
 
    '''
    avain = (rivi, jaljella, parittomilla)  # riittävät yksilöimään tilan
    try:
        return tulosmuisti[avain]
    except KeyError:
        pass
 
    if 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  # ruutuja rivillä (1, 1, 2, 2, 3, ...)
    yht = 0
 
    if ruutuja % 2:
        # ollaan parittomalla rivillä
        if ruutuja > parittomilla:
            # vielä on ruutuja jäljellä, asetetaan lähetti sille
            yht += (ruutuja - parittomilla) * \
                   lkm(rivi + 1, jaljella - 1, parittomilla + 1, parillisilla)
    else:
        # ollaan parillisella rivillä
        if ruutuja > parillisilla:
            # lähetti sopii, siis asetetaan
            yht += (ruutuja - parillisilla) * \
                   lkm(rivi + 1, jaljella - 1, parittomilla, parillisilla + 1)
 
    # ei aseteta lähettiä -laskuhaara
    yht += lkm(rivi + 1, jaljella, parittomilla, parillisilla)
 
    tulos = yht % TULOKSEN_JAKAJA
    tulosmuisti[avain] = tulos
    return tulos
 
print(lkm(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: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED