JZOJ 2196. 【中山市选2010】生成树

JZOJ 2196. 【中山市选2010】生成树
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码  

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说JZOJ 2196. 【中山市选2010】生成树,希望能够帮助大家进步!!!

题目

Description

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

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

  注意:在给定的n五角形圈中所有顶点均视为不同的顶点。

  

          图0  4-五角形圈的示意图

 

 

Input

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

Output

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

 

Sample Input

1
2

Sample Output

40

 

Data Constraint

 

分析

  •    画画图可以发现首先必须割五边形中的一条,然后n边形中也必须割一条
  • so 4*5^n-1*n

 

代码

 1 #include<cstdio>  
 2 #include<cstdlib>  
 3 #include<cstring>  
 4 #include<iostream>  
 5 #include<algorithm>  
 6 using namespace std;  
 7   
 8 const int mod=2007;  
 9 int qk(int x,int t)  
10 {  
11     int ret=1;  
12     while (t)  
13     {  
14         if (t&1) ret=(ret*x)%mod;  
15         x=(x*x)%mod;t>>=1;  
16     }return ret;  
17 }  
18 int main()  
19 {  
20     freopen("count.in","r",stdin);  
21     freopen("count.out","w",stdout);  
22     int n,ans,T;  
23     scanf("%d",&T);  
24     while (T--)  
25     {  
26         scanf("%d",&n);  
27         ans=(((4*qk(5,n-1))%mod)*n)%mod;  
28         printf("%d\n",ans);  
29     }return 0;  
30 }  

 

 

转载于:https://www.cnblogs.com/zjzjzj/p/10701593.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29902

发表评论