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>