[UVA][formula] 10843 - Anne's game
Anne's game
Time Limit: 2 seconds
|
Lily: "Chantarelle was part of my exotic phase." Buffy: "It's nice. It's a mushroom." Lily: "It is? That's really embarrassing." Buffy: "Well, it's an exotic mushroom, if that's any comfort." |
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.
| Sample Input | Sample Output |
3 1 2 3 |
Case #1: 1 Case #2: 1 Case #3: 3 |
Problemsetter: Igor Naverniouk
直接使用 Cayley's formula 公式。
#include <stdio.h>
int main() {
int testcase, cases = 0;
int n, i;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
long long ret = 1;
for(i = 0; i < n-2; i++)
ret = (ret*n)%2000000011;
printf("Case #%d: %lld\n", ++cases, ret);
}
return 0;
}