CF 1210F2 - Marek and Matching (hard version)

Rating: 3200
Tags: brute force, probabilities
Solve time: 2m 51s
Verified: no

Solution

Problem Understanding

We are given a complete probability model for an $n \times n$ bipartite graph, where each potential edge between a left vertex $\ell_i$ and a right vertex $r_j$ exists independently with probability $p_{ij}/100$. The randomness is entirely in whether each edge is present or absent.

The task is to compute the probability that the resulting random bipartite graph contains at least one perfect matching, meaning a set of $n$ disjoint edges covering every left and every right vertex exactly once.

The output is this probability written as a reduced fraction modulo $10^9+7$. Conceptually, we are summing probabilities over all graphs that admit a perfect matching.

The constraint $n \le 7$ is the key signal. The state space of all graphs has size $2^{n^2}$, which for $n=7$ is $2^{49}$, far too large for any enumeration over graphs. Even enumerating all matchings is small, since there are only $n! \le 5040$ matchings, but the difficulty is that matchings are not disjoint events: different matchings overlap heavily in their edge requirements.

A naïve attempt would be to iterate over all subsets of edges or all graphs and test bipartite matching feasibility. That immediately fails because each feasibility check is $O(n^3)$ or $O(n!)$, and there are exponentially many graphs.

A more subtle incorrect approach is to sum probabilities over matchings directly. That overcounts graphs with multiple perfect matchings, because a single graph may contain many valid matchings, so its probability mass is counted multiple times.

The real challenge is that we need the probability that at least one perfect matching exists, which is a union over all $n!$ possible matchings, but inclusion-exclusion over all subsets of matchings is still infeasible.

Approaches

The brute-force viewpoint starts from expanding the sample space over all $n^2$ edges. Each graph has probability equal to the product over included edges and excluded edges. We could check each graph for a perfect matching and sum probabilities, but that is $2^{n^2}$, which is hopeless even for $n=5$.

The key structural insight is to reverse the perspective: instead of iterating over edge subsets, we process columns (right vertices) one by one and build the state of which left vertices are already matched. This converts the problem into a DP over subsets of left vertices, which is manageable because $2^7 = 128$.

We treat the right side sequentially. After processing the first $j$ right vertices, we maintain a distribution over which subsets of left vertices are already matched. The crucial idea is that we do not care which right vertex matched which left vertex internally, only which left vertices have already been covered.

For each right vertex, we consider all possible choices of incident edges that are present, and then decide whether that vertex is used in the matching or ignored. However, instead of enumerating subsets of edges explicitly, we compress transitions by considering, for each subset of available neighbors, whether we assign this right vertex to one of the currently