Amusement Park
Contest: CEOI 2019 day 2 online mirror (unrated, IOI format)
Tags: *special, dp, math

You have been hired to supervise the project of a new amusement park. The park will have a special gimmick: directed slides that can get customers from one attraction to another quickly and in an entertaining way.

The park owner has given you the current project: a list of planned attractions and a list of slides that should be built between them. However, him being a businessman, he casually envisioned the impossible: among other things, he projected a slide coming from the Haunted Castle to the Roller Coaster, another from the Roller Coaster to the Drop Tower, and a third from the Drop Tower to the Haunted Castle. As the slides can only go downhill, it is evident why this is a problem. You don't have the luxury of ignoring the laws of physics when building the park, so you have to request changes in the project. Maybe he would accept reversing the slide between the Drop Tower and the Haunted Castle?

Formally:

- The project is a list of attractions and a list of directed slides. Each slide starts at one attraction and ends at another attraction.
- A proposal is obtained from the project by reversing the directions of some slides (possibly none or all of them).
- A proposal is legal if there is a way to assign an elevation to each attraction in such a way that every slide goes downhill.
- The cost of a proposal is the number of slides whose directions were reversed.

For a given project, find and report the sum of costs all legal proposals. Since this number may be large, output it modulo $$$998,244,353$$$.

Input format:
The first line contains two space-separated integers $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 18$$$, $$$0 \leq m \leq n(n-1)/2$$$) – the number of attractions and the number of slides, respectively. The attractions are numbered $$$1$$$ through $$$n$$$.

Then, $$$m$$$ lines follow. The $$$i$$$-th of these lines contains two space-separated integers $$$a_i$$$, $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$) denoting a slide from $$$a_i$$$ to $$$b_i$$$.

You may assume that:

- There are no self-loops. (For each $$$i$$$: $$$a_i \neq b_i$$$.)
- No slide appears twice. (For all $$$i \neq j$$$: $$$a_i \neq a_j$$$ or $$$b_i \neq b_j$$$.)
- No pair of attractions is connected in both directions. (The unordered pairs $$$\{a_i, b_i\}$$$ are distinct.)

Output format:
Output one line with a single integer, the sum of costs of all legal proposals modulo $$$998,244,353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 1024.0 MB

Note:
Scoring:
Subtask 1 (7 points): $$$n \leq 3$$$

Subtask 2 (12 points): $$$n \leq 6$$$

Subtask 3 (23 points): $$$n \leq 10$$$

Subtask 4 (21 points): $$$n \leq 15$$$

Subtask 5 (37 points): no additional constraints

In the first example, there are two proposals:

- The slide direction is not flipped. This proposal has cost $$$0$$$.
- The slide direction is flipped. This proposal has cost $$$1$$$.

In the second example, there are eight proposals with the slide directions as follows:

- $$$1 \rightarrow 2$$$, $$$2 \rightarrow 3$$$, $$$1 \rightarrow 3$$$ (cost $$$0$$$)
- $$$1 \rightarrow 2$$$, $$$2 \rightarrow 3$$$, $$$3 \rightarrow 1$$$ (cost $$$1$$$)
- $$$1 \rightarrow 2$$$, $$$3 \rightarrow 2$$$, $$$1 \rightarrow 3$$$ (cost $$$1$$$)
- $$$1 \rightarrow 2$$$, $$$3 \rightarrow 2$$$, $$$3 \rightarrow 1$$$ (cost $$$2$$$)
- $$$2 \rightarrow 1$$$, $$$2 \rightarrow 3$$$, $$$1 \rightarrow 3$$$ (cost $$$1$$$)
- $$$2 \rightarrow 1$$$, $$$2 \rightarrow 3$$$, $$$3 \rightarrow 1$$$ (cost $$$2$$$)
- $$$2 \rightarrow 1$$$, $$$3 \rightarrow 2$$$, $$$1 \rightarrow 3$$$ (cost $$$2$$$)
- $$$2 \rightarrow 1$$$, $$$3 \rightarrow 2$$$, $$$3 \rightarrow 1$$$ (cost $$$3$$$)

The second proposal is not legal, as there is a slide sequence $$$1 \rightarrow 2 \rightarrow 3 \rightarrow 1$$$. This means that the attraction $$$1$$$ has to be strictly higher than ifself, which is clearly impossible. Similarly, the seventh proposal is not legal. The answer is thus $$$0 + 1 + 2 + 1 + 2 + 3 = 9$$$.

Example input:
2 1
1 2

Example output:
1

Example input:
3 3
1 2
2 3
1 3

Example output:
9

Editorial:
Subtask 1
There are only five non-isomorphic directed graphs on at most three vertices (ignoring the isolated vertices), and the answer can be simply computed by hand.
Subtask 2
As $$$m \leq {7 \choose 2} = 21$$$, we can enumerate all $$$2^m$$$ reorientations, check whether they are acyclic and sum their cost. Time complexity is $$$\mathcal O((n+m) 2^m)$$$.
Subtask 3
Consider a permutation of vertices $$$P$$$. This permutation is a valid topological order in some reorientation of $$$G$$$. However, there may be multiple topological orders of the same graph. We can enumerate all $$$N!$$$ permutations, and sum the cost of all distinct reorientations - each one is represented as a bitmask of flipped edges, and those are put into set. There are at most $$$45$$$ edges, so $$$64$$$-bit integer is sufficient and easy to implement option, where __builtin_popcountll returns the cost the reorientation. Time complexity is $$$O(m n!)$$$
Subtask 4
$$$\mathcal O(4^n)$$$ solution. Will be described later.
Subtask 5
Let's first solve the problem of counting the number of acyclic reorientations using the topological orders as outlined in the previous subtask. Recall Kahn's algorithm for finding topological ordering: while there are vertices in the graph, pick a vertex with in-degree $$$0$$$ and remove it along with all incident arcs. With proper bookkeeping, this can be implemented in $$$\mathcal O(n + m)$$$.
We will consider only certain topological orders called canonical. We call a topological order canonical, if at every step of Kahn's algorithm the available vertex with the smallest index is picked. Clearly, each acyclic graph has exactly one canonical topological order, so we can restrict ourselves to counting those.
We will use the following dynamic programming approach - let $$$D[A][B]$$$ be the number of ways of permuting the vertices of $$$A$$$, such that this order is a prefix of some canonical topological order, and the set of vertices that can have zero indegree equals to $$$B$$$. The transition from $$$D[A][B]$$$ consists of trying all possible choices of vertex c from the set $$$B$$$ to be the next vertex in the canonical topological order. To which state $$$D[A'][B']$$$ do we transition?
The case of $$$A'$$$ is simple: $$$A' := A \cup \{c\}$$$
What happens to $$$B'$$$? All vertices with smaller index than $$$c$$$ clearly can't have indegree zero anymore, as otherwise we would not have picked $$$c$$$. However, we must also remove all outgoing edges from $$$c$$$. To do this, observe that all neighbours of $$$c$$$ that are not already in $$$A$$$ get their indegree decreased. In particular, it may become zero, so the vertex is added to $$$B'$$$:
$$$$$$B' := (B \setminus \{0,1,...,c-1\}) \cup (N(c) \setminus A)$$$$$$
where $$$N(c)$$$ is the set of neighbours of $$$c$$$.
How to sum the costs of the reorientations? We maintain a second DP table $$$C[a][b]$$$. When picking a vertex v, we have to flip all outgoing arcs with their endpoint in A. In other words
$$$$$$C[A'][B'] += C[A][B] + D[A][B] * |N^{+}(c) \cap A|$$$$$$
where $$$N^{+}(c)$$$ is the set of vertices to which there is an arc from $$$c$$$ in graph $$$G$$$.
Alternatively, we can observe that for each acyclic reorientation $$$H$$$ the reverse orientation $$$H^R$$$ is also acyclic and the sum of costs of these two orientations is $$$m$$$. As a result, the answer is $$$count \cdot m / 2$$$.
As $$$A$$$ is always disjoint with $$$B$$$, there are $$$3^n$$$ states and each state has at most n transitions. These can be performed using bitmasks, so the total runtime can be bounded from above by $$$O(n 3^n)$$$.
A lot of states are in fact unreachable. Can you prove a tighter upper bound than the one we have shown?