219
Cerința
Se dă n
un număr natural nenul. Să se afle câte soluții are ecuația x
1
+x
2
+...+x
n
=0
în mulțimea {-1,0,1}
.
Date de intrare
Fișierul de intrare necuatie.in
conține pe prima linie numărul n
.
Date de ieșire
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
1 ≤ n ≤ 2000
Exemplu
necuatie.in
3
necuatie.out
7
Explicație
Soluțiile ecuației x
1
+x
2
+x
3
=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)
.
#include <bits/stdc++.h> using namespace std; #define MOD 555557 ifstream cin("necuatie.in"); ofstream cout("necuatie.out"); int n , S = 1; int Invers(int a) { int r = 1 , n = MOD - 2; while(n > 0) { if(n % 2 == 1) r = 1LL * r * a % MOD; a = 1LL * a * a % MOD; n /= 2; } return r; } int combinari(int n , int k) { int P = 1 , Q = 1; for(int i = 1 ; i <= k ; i++) { P = 1LL * P * (n - i + 1) % MOD; Q = 1LL * Q * i % MOD; } return 1LL * P * Invers(Q) % MOD; } int main() { cin >> n; for(int i = 1 ; i <= n / 2; i++) S = (S + 1LL * combinari(n , i) * combinari(n - i , i) % MOD) % MOD; cout << S; }
Comentarii