11276 - Magical Seven

[sclo]

I don't quite understand the sample output.
For the case of 2xn grid, I calculated that the number of perfect matchings should be 21 (see problem 11270), and the number of hamiltonian cycles + components cycles should be 8. The total I get is 0029.
Can someone verify this?

[baodog]

It should be 30.
If it's both a Hamiltonian Cycle, and component cycles,
you have to count it twice.

So it's 30. Notice it says A+B+C, not union of sets, but addition
of total counts.

It's 21+8+1=30.

[sclo]

Thanks for the reply.
Oh, now I need to think about how to explicitly count hamiltonion cycles.
By the way, I think my solution should be quite close now, just need a bit more stuff.
Currently my algorithm is O(2^18 * log(n/2))

[sclo]

It turns out counting hamiltonian cycles in grid graphs is quite a nasty problem because of connectivity issues.

[baodog]

Hint

When considering Hamiltonian cycles,
the complexity without precomputation becomes

~ k1*2^36*log(n/2))

Using your method, which is too slow.
However, if you do about 1 to 2 hours of precomputation
(on Pentium M 1.7ghz),

you can bring it down to

~ k2*36^3 * log(n/2)

Which runs comfortably in time .

[sclo]

Thanks, I believe that I have now found the deg 36 generation function for the hamiltonian cycle. It is quite nasty indeed.