bzoj2467 [中山市选2010]生成树

Description

有一种图形叫做五角形圈。一个五角形圈的中心有1个由n个顶点和n条边组成的圈。在中心的这个n边圈的每一条边同时也是某一个五角形的一条边，一共有n个不同的五角形。这些五角形只在五角形圈的中心的圈上有公共的顶点。如图0所示是一个4-五角形圈。

现在给定一个n五角形圈，你的任务就是求出n五角形圈的不同生成树的数目。还记得什么是图的生成树吗？一个图的生成树是保留原图的所有顶点以及顶点的数目减去一这么多条边,从而生成的一棵树。
注意：在给定的n五角形圈中所有顶点均视为不同的顶点。
Input

输入包含多组测试数据。第一行包含一个正整数T，表示测试数据数目。每组测试数据包含一个整数n( 2<=N<=100)，代表你需要求解的五角形圈中心的边数。

Output

对每一组测试数据，输出一行包含一个整数x，表示n五角形圈的生成树数目模2007之后的结果。

Sample Input
1
2

Sample Output
40

分析:
精巧的组合数学

整个图是由n个环组成的
我们需要拆掉一些边，让图变成一棵树
最好处理的就是在外围的五边形上，每个五边形都拆掉一条边


无论拆掉的是哪条边
最后会变成一个环套树
那我们就需要在这个环上再拆一条边
拆完边后，我们可以发现最后的情况一定是
每个五边形上拆掉任意一条边
其中有一个五边形上拆掉了两条边，这两条边中一定有一条在中间的环上

最后的答案就变成了一个柿子（式子）:

拆掉两条边的五边形有n种选择，
这个多边形一定有一条边拆在中间，剩下一条边有4种选择
剩下的n-1个五边形都有5种拆边的方式

4*n*5^(n-1)

这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const int mod=2007;
int n;

int KSM(int a,int b)
{
    int t=1;
    while (b)
    {
        if (b&1)
           t=(t*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return t;
}

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        int ans=KSM(5,n-1);
        ans=(ans*4*n)%mod;
        printf("%d
",ans);
    }
    return 0;
}