View source for 4284 - Kx Desc

Considerăm trei numere naturale nenule: n, k şi x. Denumim o kx-descompunere a numărului n o posibilitate de a scrie numărul n ca sumă de k numere naturale nenule astfel încât diferenţa între oricare doi termeni ai sumei este cel puţin egală cu x.

==Cerința==
Fiind date trei numere naturale n, k şi x, să se determine câte kx-descompuneri distincte există. Două kx-descompuneri sunt distincte dacă diferă prin cel puţin un termen.

==Date de intrare==
Fișierul de intrare kx_desc.in conține pe prima linie trei valori naturale nenule reprezentând numerele n, k şi x.

==Date de ieșire==
Fișierul de ieșire kx_desc.out va conține o singură valoare reprezentând restul împărţirii numărului de kx-descompuneri distincte la numărul 10007.

==Restricții și precizări==
Pentru 20% din teste 0 < n ≤ 200; pentru celelalte 80% din teste, 200 < n ≤ 10000;
1 ≤ x, k ≤ n
==Exemplul 1==:
kx_desc.in

20 2 3
kx_desc.out

8
==Explicație==
Numărul de kx-descompuneri în acest caz este 8. Acestea sunt formate din numerele 1 şi 19; 2 şi 18; 3 şi 17; 4 şi 16; 5 şi 15; 6 şi 14; 7 şi 13; 8 şi 12.

==Exemplul 2==:
kx_desc.in

2000 19 7
kx_desc.out

3184
==Rezolvare==
MOD = 10007

def kx_descompuneri(n, k, x):
    dp = [[0] * (x + 1) for _ in range(n + 1)]

    for i in range(x + 1):
        dp[i][i] = 1

    for i in range(x + 1, n + 1):
        for j in range(1, x + 1):
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - x - 1][j]) % MOD

    rezultat = 0
    for i in range(n - x + 1, n + 1):
        rezultat = (rezultat + dp[i][x]) % MOD

    return rezultat

if __name__ == "__main__":
    # Citim datele de intrare
    n, k, x = map(int, input().split())

    # Calculăm rezultatul și îl afișăm
    rezultat = kx_descompuneri(n, k, x)
    print(rezultat)
python kx_desc.py < kx_desc.in