Editing 1012 - aranjare


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

= Date de intrare =
Programul citește de la tastatură numerele <code>n</code> și <code>p</code>, separate prin spații.

= Date de ieșire =
Programul va afișa pe ecran numărul <code>m</code>, reprezentând numărul de moduri cerut. Deoarece acest număr ar putea fi foarte mare, rezultatul se va afișa modulo <code>100019</code>.

= Restricții și precizări =

* <code>1 ≤ p ≤ n ≤ 100.000</code>
* locurile și persoanele sunt numerotate de la <code>1</code> la <code>n</code>

= Exemplu: =
Intrare
 8 4
Ieșire
 16

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

== Rezolvare ==
<syntaxhighlight lang="python3">
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()

</syntaxhighlight>