10843 - Anne's game
For this problem, we have to find the number of labeled trees on N vertices, modulo 2000000011.
Each circle is a vertex and each line drawn is an edge. Clearly after N steps we have a connected graph with N vertices and N-1 edges. Thus the resulting graph is a tree. It can be proved that there are exactly labeled trees on N vertices. Since we only have to print the answer modulo 2000000011, this can be safely calculated without the use of BigNum.
While the answer fits into a 32-bit signed integer, using 64-bit integers is recommended when computing the result to avoid overflow.
The answer can be computed in time using Repeated Squaring.
An exceptionally nice proof that the number of labeled trees on N vertices is can de achieved using the Prufer code of a tree.
3 1 2 3
Case #1: 1 Case #2: 1 Case #3: 3