How Many Orders Visit Everything
An undirected graph on n vertices is given. Count the sequences v1, v2, ..., vn that use
every vertex exactly once and in which each consecutive pair is joined by an edge.
Two sequences that are reverses of each other count separately. Print the count modulo
1000000007.
4 vertices in a cycle 1-2-3-4-1 -> 8
4 vertices in a star -> 0 the centre would have to be used twice
## The same table as 581
This is problem 581 with min replaced by +, and the starting cost replaced by a starting
count of 1.
dp[mask][u] = the number of orders that use exactly the vertices in mask and end at u
dp[1<<i][i] = 1 for every i
dp[mask | 1<<v][v] += dp[mask][u] when u is in mask and u-v is an edge
answer = sum over u of dp[full][u]
Every vertex is a possible start, so there are n base cases here rather than the single one
in 581.
## Why the answer counts both directions
A path and its reverse are different SEQUENCES, and the table counts sequences. Reporting
undirected paths would need a division by 2, which is wrong when n = 1: there is one
sequence and it is its own reverse.
The statement therefore asks for sequences, which needs no division and no special case. When a counting problem seems to want a division, check the fixed points first.
## Where the modulus goes
Reduce after every addition. The count can reach n!, which passes 10^9 at n = 13, so an
unreduced accumulator overflows well inside the constraints.
## Reading the answer
The star answers 0. Its centre lies on every edge, so any order using all four vertices would have to pass through the centre twice, and a sequence uses each vertex once.
The complete graph on 4 answers 24, which is 4!: every order works. Those two are the
extremes and are worth checking first in any implementation.
## Cost
Time O(2^n * n^2). Space O(2^n * n).
At n = 16 that is about 17 million steps.