1160 - Necuatie

From Bitnami MediaWiki

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>