Spanning trees

Revision en1, by klyn, 2020-09-28 19:01:25

Problem statement: A little girl whose name is Anne Spetring likes to play the following game. She draws a circle on paper. Then she draws another one and connects it to the first cicrle by a line. Then she draws another and connects it to one of the first two circles by a line. She continues this way until she has n circles drawn and each one connected to one of the previously drawn circles. Her circles never intersect and lines never cross. Finally, she numbers the circles from 1 to n in some random order.

How many different pictures can she draw that contain exactly n circles? Two pictures are different if one of them has a line connecting circle number i to circle number j, and the other picture does not.

INPUT: The first line of input gives the number of cases, N. N test cases follow. Each one is a line containing n (0 < n ≤ 100).

OUTPUT: For each test case, output one line containing ‘Case #x:’ followed by X, where X is the remainder after dividing the answer by 2000000011.

I just want to know, what is the formula to solve this problem and why it will work?

#### History

Revisions

Rev. Lang. By When Δ Comment
en4 klyn 2020-09-29 13:51:55 0 UPDATE: Got it!
en3 klyn 2020-09-28 19:58:22 5 Tiny change: '011;\n\nI just want to k' -> '011;\n\nI want to k'
en2 klyn 2020-09-28 19:57:43 293
en1 klyn 2020-09-28 19:01:25 1113 Initial revision (published)