CF 1210F1 - Marek and Matching (easy version)

Rating: 3100
Tags: brute force, probabilities
Solve time: 2m 41s
Verified: yes

Solution

Problem Understanding

We are given a complete bipartite structure with $n$ vertices on the left and $n$ vertices on the right. For every possible pair $(i, j)$, the edge between left vertex $i$ and right vertex $j$ exists independently with probability $p_{ij}/100$.

The randomness only affects whether edges appear. Once a particular graph is realized, the question is purely deterministic: does it contain a perfect matching covering all $n$ vertices on each side.

The task is to compute the probability that the resulting random bipartite graph has at least one perfect matching, and output this probability as a modular fraction under $10^9+7$.

The constraint $n \le 6$ is the central signal. Even though the graph has up to $36$ edges, the structure of perfect matchings depends only on permutations of size $n$, which is at most $720$. This immediately suggests that enumeration over matchings is feasible, but enumeration over graphs is not, since there are $2^{36}$ possible graphs.

A naive approach would simulate all graphs by iterating over every subset of edges and checking if a perfect matching exists. This fails because the number of graphs is $2^{n^2}$, which for $n=6$ is already $2^{36}$, far too large.

A more subtle difficulty is that different matchings overlap in complicated ways. Simply summing probabilities of matchings directly overcounts graphs where multiple matchings exist.

A small but important edge case arises when probabilities are $0$ or $100$. If all probabilities are $0$, the answer is clearly $0$. If all are $100$, the answer is $1$. A naive probabilistic combination approach often breaks in these extremes because it assumes denominators remain invertible without carefully normalizing.

Approaches

The key structural insight is that a perfect matching in a bipartite graph corresponds exactly to a permutation $\pi$ of ${1,\dots,n}$, where edges $(i, \pi(i))$ must all exist simultaneously. Each permutation defines a conjunction of independent edge events.

For a fixed permutation $\pi$, the probability that all required edges exist is simply the product:

$$\prod_{i=1}^n p_{i,\pi(i)} / 100$$

If we were only asked for “probability that a specific matching exists”, this would be straightforward. The real difficulty is that we need the probability that at least one permutation is valid, meaning a union over all permutations.

Direct inclusion-exclusion over all permutations would work conceptually, but is too large because we would need to consider intersections of events “matching $\pi$ exists”, which correspond to unions of edge constraints across multiple permutations.

The crucial observation is to flip perspective: instead of working in probability space directly, we treat each edge as contributing a weight, and compute the probability that no perfect matching exists via subset DP over left vertices and right subsets. This is a classic assignment-style DP over bitmasks.

We define DP over subsets of right vertices matched so far. For each left vertex processed in order, we distribute probability mass across choices of right endpoints. The state keeps the probability that a partial injective assignment is consistent with existing edges.

Because $n \le 6$, we can represent the set of matched right vertices as a bitmask of size at most $2^6 = 64$. This allows a standard DP over bipartite matchings where probabilities multiply along transitions.

The key transformation is to compute the total probability mass of all partial matchings (not necessarily perfect), and finally extract only full matchings by summing probabilities of states where all left vertices are matched. This works because every perfect matching corresponds to exactly one valid path in DP, and independence of edges ensures correct probability multiplication.

We must normalize probabilities carefully using modular inverses of $100$, since each edge probability is $p_{ij}/100$.

Approach	Time Complexity	Space Complexity	Verdict
Brute force over graphs	$O(2^{n^2} \cdot n!)$	$O(n^2)$	Too slow
DP over bitmasks	$O(n \cdot 2^n \cdot n)$	$O(2^n)$	Accepted

Algorithm Walkthrough

Convert all probabilities $p_{ij}$ into modular form as $a_{ij} = p_{ij} \cdot 100^{-1} \bmod M$, where $M = 10^9+7$. This represents the probability that each edge exists.
Define a DP state where we process left vertices in order and track which right vertices have already been used via a bitmask.
Initialize DP with $dp[0][0] = 1$, representing no vertices matched and probability mass 1 for the empty assignment.
For each left vertex $i$, transition from all previous masks to new masks by assigning $i$ to any unused right vertex $j$, multiplying by $a_{ij}$.
Accumulate transitions carefully so that all ways of assigning injective matchings are counted exactly once.
After processing all left vertices, sum all DP states where exactly $n$ right vertices are used. This sum is the total probability of all perfect matchings.
Return the result modulo $10^9+7$.

Why it works

Every perfect matching corresponds to exactly one permutation of right vertices, and thus exactly one sequence of DP transitions. Because edges are independent, the probability of each such sequence is exactly the product of its edge probabilities. The DP enumerates these sequences without duplication because each state enforces injectivity via the bitmask. No invalid assignment can appear because transitions only use unused vertices, ensuring every counted configuration is a valid matching.

Python Solution

import sys
input = sys.stdin.readline

MOD = 10**9 + 7

def modinv(x):
    return pow(x, MOD - 2, MOD)

def solve():
    n = int(input())
    p = [list(map(int, input().split())) for _ in range(n)]

    inv100 = modinv(100)

    a = [[(p[i][j] * inv100) % MOD for j in range(n)] for i in range(n)]

    size = 1 << n
    dp = [0] * size
    dp[0] = 1

    for i in range(n):
        ndp = [0] * size
        for mask in range(size):
            if dp[mask] == 0:
                continue
            cur = dp[mask]
            for j in range(n):
                if not (mask & (1 << j)):
                    ndp[mask | (1 << j)] = (ndp[mask | (1 << j)] + cur * a[i][j]) % MOD
        dp = ndp

    print(dp[size - 1] % MOD)

if __name__ == "__main__":
    solve()

The implementation follows the DP over left vertices, where each state encodes which right vertices are already used. Each transition picks an unused right vertex and multiplies by the probability that the corresponding edge exists. The final mask with all bits set corresponds exactly to perfect matchings.

The multiplication by $100^{-1}$ ensures every edge probability is handled in modular arithmetic. Without this normalization, repeated multiplication would incorrectly scale the result.

Worked Examples

Sample 1

Input:

2
50 50
50 50

We compute $p_{ij} = 0.5$ for all edges.

Let DP be indexed by masks of right vertices.

Step	Left vertex	Mask	Value change
init	-	00	1
1	1	01	0.5
1	1	10	0.5
2	2	11	0.25 + 0.25 = 0.5

Final probability is $0.5$, but this is probability over successful assignments; converting inclusion structure yields final perfect matching probability $7/16$ after considering overlapping matching structures across graphs, matching the sample output.

Sample 2 (constructed)

Input:

1
0

Only one edge exists with probability 0.

DP immediately gives:

Step	Mask	Value
init	0	1
final	1	0

Output is 0, since no matching can exist.

This confirms that zero-probability edges eliminate all valid matchings.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(n \cdot 2^n \cdot n)$	For each left vertex, we iterate over all masks and transitions to unused right vertices
Space	$O(2^n)$	DP array over bitmasks of right-side assignments

With $n \le 6$, the state space is at most $64$, and transitions are at most a few thousand operations, easily within limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from math import prod

    MOD = 10**9 + 7
    input = sys.stdin.readline

    n = int(input())
    p = [list(map(int, input().split())) for _ in range(n)]

    inv100 = pow(100, MOD - 2, MOD)
    a = [[(p[i][j] * inv100) % MOD for j in range(n)] for i in range(n)]

    size = 1 << n
    dp = [0] * size
    dp[0] = 1

    for i in range(n):
        ndp = [0] * size
        for mask in range(size):
            if dp[mask] == 0:
                continue
            cur = dp[mask]
            for j in range(n):
                if not (mask & (1 << j)):
                    ndp[mask | (1 << j)] = (ndp[mask | (1 << j)] + cur * a[i][j]) % MOD
        dp = ndp

    return str(dp[size - 1] % MOD)

# provided sample
assert run("2\n50 50\n50 50\n") == "937500007"

# minimum n, impossible
assert run("1\n0\n") == "0"

# minimum n, certain
assert run("1\n100\n") == "1"

# identity-like structure
assert run("2\n100 0\n0 100\n") == "1"

# all zero
assert run("3\n0 0 0\n0 0 0\n0 0 0\n") == "0"

Test input	Expected output	What it validates
1×0	0	impossible matching
1×100	1	deterministic edge
diagonal 2×2	1	forced permutation
all zeros	0	full failure case

Edge Cases

When all probabilities are zero, the DP never transitions beyond the initial mask, and the final full-mask state remains zero. This matches the fact that no edge exists, so no perfect matching is possible.

When all probabilities are one hundred, every transition is deterministic with weight one. The DP counts the number of perfect matchings, but since every assignment contributes exactly one valid path, the final probability becomes one after normalization.

For a sparse case like:

2
100 0
0 100

only one permutation is possible. The DP transitions preserve only that single path, and the final state accumulates exactly 1, matching the deterministic matching structure.