Editing 2493 - Recc

== Enunț == 
Ana Mia are o recurență liniară de forma P[N] = A[1]*P[N-1] + A[2]*P[N-2] + A[3]*P[N-3] + A[4]*P[N-4], N ≥ 5. Studiind-o, îi vine o idee MAXIMĂ de problemă: “Pentru câte cvadriplete (P[1], P[2], P[3], P[4]) din mulțimea numerelor naturale [1, B] valoarea P[N] modulo K are valoarea X?”
== Cerința ==
Scrieți un program care citind N, B, X, K, și numerele A[i], 1 ≤ i ≤ 4 rezolvă problema Anei.
== Date de intrare ==
Fișierul de intrare reccin.txt conține pe prima linie numerele N, B, X, K, separate printr-un spațiu, iar pe a doua linie 4 numere naturale separate prin spații, reprezentând numerele A[i], 1 ≤ i ≤ 4.
== Date de ieșire == 
Fișierul de ieșire reccout.txt va conține pe prima linie numărul ANS, răspunsul problemei puse de Ana Mia.
== Restricții și precizări ==
*'''5 ≤ N ≤ 10^18'''
*'''1 ≤ B ≤ 1000'''
*'''1 ≤ K ≤ 10^9'''
*'''0 ≤ X < K'''
*numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
== Exemplul 1 ==
; reccin.txt
: 6 2 3 4
: 1 2 3 1
; reccout.txt
: 2
<br>
== Exemplul 2 ==
; reccin.txt
: 8 5 1 7
: 2 1 3 2
; reccout.txt
: 4
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#2493 - Recc
def count_quadruplets(N, B, X, K, A):
    if not (5 <= N <= 10**18) or not (1 <= B <= 1000) or not (1 <= K <= 10**9) or not (0 <= X < K):
        return "Fals"

    if N == 1:
        return 1 if X % K == A[0] else 0

    dp = [0] * (B + 1)

    for i in range(1, B + 1):
        dp[i] = (A[0] * dp[i - 1]) % K

        if i >= 2:
            dp[i] = (dp[i] + A[1] * dp[i - 2]) % K

        if i >= 3:
            dp[i] = (dp[i] + A[2] * dp[i - 3]) % K

        if i >= 4:
            dp[i] = (dp[i] + A[3] * dp[i - 4]) % K

    ans = 0
    for i in range(1, B + 1):
        if (dp[i] + X) % K == 0:
            ans += 1

    return ans


def main():
    with open("reccin.txt", "r") as f:
        N, B, X, K = map(int, f.readline().split())
        A = list(map(int, f.readline().split()))

    result = count_quadruplets(N, B, X, K, A)

    with open("reccout.txt", "w") as f_out:
        f_out.write(str(result))


if __name__ == "__main__":
    main()

</syntaxhighlight>

== Explicatie ==
Soluțiile sunt (2, 1, 2, 1) și (2, 2, 2, 1)