1160 - Necuatie
Cerința[edit | edit source]
Se dă n un număr natural nenul. Să se afle câte soluții are ecuația x1+x2+...+xn=0 în mulțimea {-1,0,1}.
Date de intrare[edit | edit source]
Fișierul de intrare necuatie.in conține pe prima linie numărul n.
Date de ieșire[edit | edit source]
Fișierul de ieșire necuatie.out va conține pe prima linie numărul S, reprezentând numărul soluțiilor ecuației modulo 555557.
Restricții și precizări[edit | edit source]
1 ≤ n ≤ 2000
Exemplu:[edit | edit source]
necuatie.in
3
necuatie.out
7
Explicație[edit | edit source]
Soluțiile ecuației x1+x2+x3=0 în mulțimea { -1 , 0 , 1 } sunt: (0,0,0) , (0,1,-1) , (0,-1,1) , (1,0,-1) , (-1,0,1) , (1,-1,0) , (-1,1,0).
Încărcare soluție[edit | edit source]
Lipește codul aici[edit | edit source]
<syntaxhighlight lang="python" line="1"> MOD = 555557 n = int(input()) S = 1
def Invers(a):
r = 1
n = MOD - 2
while n > 0:
if n % 2 == 1:
r = (r * a) % MOD
a = (a * a) % MOD
n //= 2
return r
def combinari(n, k):
P = 1
Q = 1
for i in range(1, k+1):
P = (P * (n - i + 1)) % MOD
Q = (Q * i) % MOD
return (P * Invers(Q)) % MOD
for i in range(1, n // 2 + 1):
S = (S + (combinari(n, i) * combinari(n - i, i)) % MOD) % MOD
print(S)
</syntaxhighlight>