4194 - EchipaFB

Cerinta

Într-o şcoală sunt F fete şi B băieţi. Pentru fiecare valoare a lui K de la 1 la F+B, aflaţi în câte moduri se poate alcătui o echipă formată din K elevi, care să conţină un număr impar de fete.

Date de intrare

Programul citește de la tastatură numerele F şi B.

Date de iesire

Programul va afișa pe ecran, pentru fiecare K de la 1 la F+B, numărul de moduri în care putem forma echipa, modulo 998244353.

Restrictii si precizari

• 1 ⩽ F,B ⩽ 100.000

Exemplul 1

Intrare

3 2

Iesire

Datele introduse corespund restrictiilor impuse

3 6 4 2 1

Exemplul 2

Intrare

-10 7

Iesire

Datele introduse nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> MOD = 998244353

def comb(n, k):

   # Calculează coeficientul binomial C(n, k) % MOD folosind metoda combinatorică modulară
   result = 1
   for i in range(1, k + 1):
       result = (result * (n - i + 1) * pow(i, -1, MOD)) % MOD
   return result

def count_ways(F, B):

   # Calculăm numărul de moduri pentru fiecare K de la 1 la F+B
   for K in range(1, F + B + 1):
       # Numărul de moduri în care putem forma o echipă cu un număr impar de fete
       # este dat de suma combinărilor C(F, i) * C(B, K - i) pentru i de la 1 la min(K, F)
       ways = 0
       for i in range(1, min(K, F) + 1, 2):
           ways = (ways + comb(F, i) * comb(B, K - i)) % MOD
       
       print(ways)

if __name__ == "__main__":

   # Citim numerele F și B de la tastatură
   F = int(input("Introduceți numărul de fete (F): "))
   B = int(input("Introduceți numărul de băieți (B): "))

   # Calculăm și afișăm rezultatele
   count_ways(F, B)

</syntaxhighlight>

Explicatie

Să notăm cu A,B,C fetele şi cu X,Y băieţii. Pentru K=1 echipele pot fi A, B, respectiv C. Pentru K=2: AX, AY, BX, BY, CX, CY. Pentru K=3: AXY, BXY, CXY, ABC. Pentru K=4: ABCX, ABCY. Pentru K=5: ABCXY.