0707 - Sum K

sumk este un joc de perspicacitate, cu N stagii numerotate de la 1 la N. Un joc se termină cu succes dacă jucătorul a parcurs în ordine, de la 1 la N, toate cele N stagii ale jocului şi în fiecare stagiu a obţinut exact K puncte. Fiecare stagiu are N niveluri, numerotate de asemenea de la 1 la N. Jucătorul are posibilitatea să câştige 0, 1, …, K puncte pe oricare nivel al stagiului curent.

Dacă jucătorul se găseşte în stagiul i pe nivelul j și numărul total de puncte obţinute până în acel moment în acest stagiu este mai mic decât K, el va trece în mod obligatoriu pe nivelul j+1 al stagiului i. Dacă jucătorul primește cel puţin un punct pe nivelul j și astfel punctajul său în stagiul i devine exact K, atunci jucătorul trece în mod automat pe nivelul j al stagiului i+1 sau termină jocul cu succes dacă i=N.

Cerința

Cunoscând numărul N de stagii ale jocului şi numărul K de puncte care trebuie să fie obţinute în fiecare stagiu, să se determine numărul de posibilităţi modulo 578537 pentru ca jocul să se termine cu succes.

Date de intrare

Fișierul de intrare sumkIN.txt conține pe prima linie două numere naturale N K cu semnificația descrisă anterior.

Date de ieșire

Fișierul de ieșire sumkOUT.txt va conține pe prima linie un singur număr natural P reprezentând numărul total de posibilităţi modulo 578537 pentru ca jocul să se termine cu succes. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 1 ≤ K ≤ N ≤ 500
• Fie x punctajul final într-un stagiu oarecare. Atunci dacă x ≠ K, jocul se termină cu eșec.
• Pentru 20% din teste, K ≤ N ≤ 10, iar pentru 30% din teste, K≤N≤100

Exemplu 1:

sumkIN.txt

2 2

sumkOUT.txt

5

Exemplu 2:

sumkIN.txt

2 3

sumkOUT.txt

Datele nu corespund restrictiilor impuse.

Rezolvare

def calcul(z1, z2, n, a):
    x = [0] * 502
    for j in range(1, n + 1):
        s = 0
        for i in range(1, j + 1):
            t = z1[i]
            t = (t * z2[j - i + 1]) % a
            s = (s + t) % a
        x[j] = s
    for j in range(1, n + 1):
        z1[j] = x[j]

def main():
    try:
        with open("sumkIN.txt", "rt") as fin:
            n, k = map(int, fin.readline().split())
    except Exception as e:
        with open("sumkOUT.txt", "wt") as fout:
            fout.write("Eroare la citirea datelor de intrare.")
        return

    if not (1 <= k <= n <= 500):
        with open("sumkOUT.txt", "wt") as fout:
            fout.write("Datele nu corespund restrictiilor impuse.")
        return

    r = [0] * 502
    z = [0] * 502
    r[1] = 1
    a = 578537

    for j in range(1, k + 1):
        for i in range(2, n + 1):
            r[i] = (r[i - 1] + r[i]) % a

    v = n
    z[1] = 1
    while v != 0:
        if v % 2 == 1:
            calcul(z, r, n, a)
        calcul(r, r, n, a)
        v = v // 2

    s = 0
    for i in range(1, n + 1):
        s = (s + z[i]) % a

    with open("sumkOUT.txt", "wt") as fout:
        fout.write(f"{int(s)}")

if __name__ == "__main__":
    main()