[ZSOI 生成树]组合数学

【题目】

Description

  有一种图形叫做五角形圈。一个五角形圈的中心有1个由n个顶点和n条边组成的圈。在中心的这个n边圈的每一条边同时也是某一个五角形的一条边,一共有 n个不同的五角形。这些五角形只在五角形圈的中心的圈上有公共的顶点。如图0所示是一个4-五角形圈。
现在给定一个n五角形圈,你的任务就是求出n五角形圈的不同生成树的数目。还记得什么是图的生成树吗?一个图的生成树是保留原图的所有顶点以及顶 点的数目减去一这么多条边,从而生成的一棵树。
注意:在给定的n五角形圈中所有顶点均视为不同的顶点。

Input

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

Output

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

Sample Input

1
2

Sample Output

40

【算法分析】
把每一个五边形当成一个状态,并按顺时针进行编号。
那么第i个状态和其它状态连接的就只有在中心圈中对应的两个点。
然后我们考虑最终必然是有且仅有一个状态是中心圈对应的点并非通过该五边形连接的。
这个特殊的状态必然是去掉圈上边和剩下四条边的任意一条。所以有4种删边法。
除了这个状态以后,其它状态都是独立的,并且应当只去掉1条边。
一共五条边,所以就是有5种情况。
所以,根据乘法原理,答案应该是4*5^(n-1)。
又由于那个特殊的状态可以分步在n个状态中的任意一个,并且所得结果必然都是不同的。
所以最终结果:4*n*5^(n-1)。
【CODE】
#include #include #include const int mod=2007;
int n,ans;

void solve(){
ans=1;
for (int i=1;i ans=ans*4%mod;
ans=ans*n%mod;
printf("%dn",ans);
}

int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
scanf("%d",&n);
solve();
}
}

留下评论

您的电子邮箱地址不会被公开。