Editing 3508 - Bal

== Cerinta ==

La balul din acest an participă '''n''' băieți și '''n''' fete, numerotați de la 1 la n. Compatibilitățile dintre aceștia pot fi reprezentate sub forma unui graf bipartit. Fie mat matricea de adiacentă. Atunci, băiatul '''i''' se poate cupla cu fata '''j''' doar dacă sunt compatibili, adică '''mat[i][j] = 1'''. Aflați numărul de moduri de a forma cele '''n''' cupluri.

== Date de intrare ==

Programul citește de la tastatură numărul '''n''', iar apoi matricea de adiacență.

== Date de iesire ==

Programul va afișa pe ecran numărul de moduri de a forma cuplurile, modulo '''1.000.000.007'''.

== Restrictii si precizari ==

*1 < n < 25

== Exemplul 1 ==
;Intrare
:3
:0 1 1
:1 0 1
:1 1 1
;Iesire
:Datele introduse corespund restrictiilor impuse
:3

== Exemplul 2 ==
;Intrare
:3
:-5 34 0
:3 87 0
:0 0 -1
;Iesire
:Datele introduse nu corespund restrictiilor impuse


== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
MOD = 1000000007

def numar_moduri_cuplare(n, matrice):
    dp = [[0] * (1 << n) for _ in range(n + 1)]
    dp[0][0] = 1

    for i in range(1, n + 1):
        for mask in range(1 << n):
            num_bits = bin(mask).count('1')

            for j in range(n):
                if matrice[i-1][j] == 1 and (mask & (1 << j)) == 0:
                    dp[i][mask | (1 << j)] = (dp[i][mask | (1 << j)] + dp[i-1][mask]) % MOD

    rezultat = sum(dp[n])
    return rezultat % MOD

def verificare(n, matrice, rezultat):
    if not (1 < n < 25):
        return False

    if rezultat < 0 or rezultat >= MOD:
        return False

    for i in range(n):
        for j in range(n):
            if matrice[i][j] not in {0, 1}:
                return False

    return True

# Citire date de intrare
n = int(input("Introduceți numărul n: "))
matrice_adiacenta = [list(map(int, input().split())) for _ in range(n)]

# Calcul și afișare rezultat
rezultat = numar_moduri_cuplare(n, matrice_adiacenta)

# Verificare și afișare rezultat
if verificare(n, matrice_adiacenta, rezultat):
    print(rezultat)
else:
    print("Datele introduse nu corespund restrictiilor impuse.")


</syntaxhighlight>

== Explicatie ==

Cele 3 modalități sunt:
:(1, 2), (2, 1), (3, 3)
:(1, 2), (2, 3), (3, 1)
:(1, 3), (2, 1), (3, 2)