GCJ Practice Contest Problem C:

In this problem, u r asked to calculate the number of all the Hamiltonian Circles in complete graph only with at most 15 forbidden edges.

We know, finding the Hamiltonian Circles is a NP problem, how can we count all the Hamiltonian Circles in a graph with so many edges?

First, let us think about this problem. Give u a complete graph with N vertexes , can u tell me how many Hamiltonian Circles exist in it?

We can easily find that number will be (N-1)! / 2.

And back to the original problem, we find that the forbidden edges are very small. So we come up with an idea, we can use the number of Hamiltonian Circles in a complete graph minus those circles using forbidden edges.

Code