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

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.")

Explicatie

Cele 3 modalități sunt:

(1, 2), (2, 1), (3, 3)

(1, 2), (2, 3), (3, 1)

(1, 3), (2, 1), (3, 2)