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