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

Exemplul 2

reccin.txt

8 5 1 7

2 1 3 2

reccout.txt

4

Rezolvare

#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()

Explicatie

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