1012 - aranjare

Cerința

Dorel tocmai a învățat la școală despre permutări. El a reținut faptul că n persoane pot fi aranjate pe n locuri în n! moduri, unde . Pentru a vă pune pe voi la încercare Dorel mai alege un număr p și vă întreabă în câte moduri putem aranja n persoane numerotate de la 1 la n pe n locuri, numerotate şi ele de la 1 la n, astfel încât suma dintre numărul persoanei și numărul locului să fie divizibilă cu p?

Date de intrare

Programul citește de la tastatură numerele n și p, separate prin spații.

Date de ieșire

Programul va afișa pe ecran numărul m, reprezentând numărul de moduri cerut. Deoarece acest număr ar putea fi foarte mare, rezultatul se va afișa modulo 100019.

Restricții și precizări

• 1 ≤ p ≤ n ≤ 100.000
• locurile și persoanele sunt numerotate de la 1 la n

Exemplu:

Intrare

8 4

Ieșire

16

Explicație

Avem 8 persoane și 8 locuri. Persoanele 1 și 5 se pot așeza pe locurile 3 și 7 în 2! moduri, persoanele 2 și 6 pe locurile 2 și 6 în 2! moduri, persoanele 3 și 7 pe locurile 1 și 5 în 2! moduri, iar persoanele 4 și 8 pe locurile 4 și 8 în 2! moduri. În total vom avea 2 4 =16 moduri de aranjare.

Rezolvare

MOD = 100019  

def count_valid_arrangements(n, p):
    total_arrangements = 0
    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

    dp[1][1] = 1

    for i in range(2, n + 1):
        for j in range(1, n + 1):
            current_arrangements = 0

            if (i + j) % p == 0:
                current_arrangements += dp[i - 1][j]

                if i != j:
                    current_arrangements += dp[i][j - 1]

            dp[i][j] = current_arrangements

    for j in range(1, n + 1):
        total_arrangements += dp[n][j]

    return total_arrangements % MOD

def main():
    n, p = map(int, input().split())

    valid_arrangements = count_valid_arrangements(n, p)
    print(valid_arrangements)

if __name__ == "__main__":
    main()