UVA 11609 - Anne's game cayley定理

时间：2024-11-13 16:05:56

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
3
1
2
3
Sample Output
Case #1: 1
Case #2: 1
Case #3: 3

题意：给出n，问说有n个节点构成的标号树有多少种。

题解：此定理说明用n-1条边将n个一致的顶点连接起来的联通树的个数为n^(n-2)，也可以这样，将n个城市连接起来的树状公路网络有n^(n-2)种方案。所谓树状，指的是用n-1条边将n个顶点构成一个连通图。当然，建造一个树状的公路网络将n个城市连接起来，应求其中长度最短、造价最省的一种，或效益最大的一种。Cayley定理只是说明可能方案的数目。

//meek

#include<bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <cmath>

#include <string>

#include <cstring>

#include <algorithm>

#include<map>

#include<queue>

using namespace std ;

typedef long long ll;

#define mem(a) memset(a,0,sizeof(a))

#define pb push_back

#define fi first

#define se second

#define MP make_pair

const int N=;

const ll INF = 1ll<<;

const int inf = ;

const int MOD =   ;

ll quick_pow(ll x,ll p) {

    if(!p) return ;

    ll ans = quick_pow(x,p>>);

    ans = ans*ans%MOD;

    if(p & ) ans = ans*x%MOD;

    return ans;

}

int main() {

    int cas;

    ll n;

    scanf("%d",&cas);

    for(int i=;i<=cas;i++) {

        scanf("%lld",&n);

        if(n< 2ll)  printf("Case #%d: %lld\n",i,1ll);

        else printf("Case #%d: %lld\n",i,quick_pow(n,n-));

    }

    return ;

}

daima

相关文章