UVA10843——Anne\'s game

男娘i 2022-08-09 13:46 18阅读 0赞

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.”

Joss Whedon, "Anne".

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

Case \#1: 1

Case \#2: 1

Case \#3: 3

题意：题目说画圈，实际上圈可以看成是点，然后就是求n个点，可以接连出多少种不同的生成树的问题了！

思路：Caylay定理，网上能找到证明，结果为n的n-2次方，然后利用快速二分幂求模去求解（以前总结的[快速二分幂求模][Link 1]）。

code：

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    typedef long long ll;
    const int mod=2000000011;
    int T,n;
    
    ll big_mod(int a,int b)  //关键实现函数，以前总结
    {
         
        ll ans=1,t=a;
        while(b)
        {
         
           if(b&1) ans=ans*t%mod;
           t=t*t%mod;
           b>>=1;
        }
        return ans%mod;
    }
    int main()
    {
         
        scanf("%d",&T);
        for (int ca=1;ca<=T;ca++)
        {
         
            int ans=1;
            scanf("%d",&n);
            if (n>1) ans=big_mod(n,n-2);
            printf("Case #%d: %d\n",ca,ans);
        }
    }

[Link 1]: http://dedream.blog.163.com/blog/static/2434830452015627102416209/