## Editorial for DMOPC '21 Contest 4 P4 - Christmas Graph

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

#### Subtask 1

This subtask was created to reward brute force solutions.

**Time Complexity:**

#### Subtask 2

There are many possible solutions with quadratic time complexity, of which we present one. First of all, let's direct all the edges added towards the respective randomly chosen nodes, so that the result becomes a functional graph. By linearity of expectation, the expected number of components is equivalent to , where is the expected number of components of size . To compute , assume we know the number of connected functional graphs of size with no self-loops . Then, for any of the sets of nodes, the probability that they form a single component is

because there are ways to have the nodes in the set form a component and total ways to direct edges between the nodes not in the set. So, again by linearity of expectation, can be expressed as

It remains to calculate for all values of . Let's first initialize all to and then subtract away the number of graphs with more than a single component. We now do the subtractions by establishing recursive relations. For any fixed , focus on the component of a single node . If there are nodes in the component of node , then there are ways to choose the nodes in the component of , different ways for them to form a component, and total ways to direct edges between the nodes not in 's component. So, for every from to , we should subtract

from , which concludes the solution.

**Time Complexity:**

#### Subtask 3

It is helpful to note that the number of components in a functional graph is equal to the number of cycles in the graph. We may therefore calculate the expected number of cycles instead. By linearity of expectation, the expected number of cycles is equivalent to , where is the expected number of cycles of size . Note that for any set of nodes, the probability that they form a cycle is because there are cycles of length and each of the nodes has a chance of pointing towards the correct node that comes next in the cycle. So, again by linearity of expectation, can be expressed as

This can easily be computed in constant time with some precomputation.

**Time Complexity:**

## Comments