How Many Ways to Pair Everyone Up
n people are given, with n even, together with the list of pairs who are willing to work
together. Count the ways to split everyone into n / 2 working pairs, using only willing
pairs. Every person is in exactly one pair.
Two splits are the same when they use the same set of pairs; the order of the pairs does not
matter. Print the count modulo 1000000007.
4 people in a cycle 1-2 2-3 3-4 4-1 -> 2 {1-2, 3-4} and {2-3, 4-1}
6 people, all pairs willing -> 15
## The duplicate problem
The obvious recursion picks any unused person, pairs them with anyone available, and recurses.
It counts every split many times over, because the same set of pairs can be built in any
order: {1-2, 3-4} arrives once as 1 first and once as 3 first.
Dividing at the end is awkward and easy to get wrong.
## Always take the LOWEST free person
Fix the rule: at each step, find the lowest-numbered person not yet paired, and choose their partner. That person's pair must be decided sooner or later, so nothing is lost; and the order of construction is now forced, so nothing is counted twice.
That single rule is why this topic's partition problems have no division anywhere, and it reappears unchanged in 586, 591 and 592.
## The table
dp[mask] = the number of ways to pair up exactly the people in mask
dp[0] = 1
let i = the lowest index NOT in mask
for each j > i not in mask with i and j willing:
dp[mask | (1<<i) | (1<<j)] += dp[mask]
The answer is dp[full].
Note that j > i is automatic once i is the lowest free index, but writing it makes the
intent clear and costs nothing.
## Why the mask alone is enough
A partial pairing affects the future only through WHO is still free. Nothing about how the used people were paired matters. That is optimal substructure in a set-valued state, and it is what makes a single index sufficient here where 581 needed two.
## Boundaries
An odd n is excluded by the constraints. With n = 2 the answer is 1 if the pair is willing
and 0 otherwise.
The complete graph on 6 answers 15, which is the double factorial 5 * 3 * 1. That is a good
first check: if the count for a complete graph on n is not (n-1)!!, the duplicate rule is
not being applied.
## Cost
Time O(2^n * n). Space O(2^n).