首页 > 代码库 > NYOJ127 星际之门(一)(最小生成数的个数+高速幂)
NYOJ127 星际之门(一)(最小生成数的个数+高速幂)
题目描写叙述:
http://acm.nyist.net/JudgeOnline/problem.php?pid=127
- 能够证明。修建N-1条虫洞就能够把这N个星系连结起来。
如今。问题来了。皇帝想知道有多少种修建方案能够把这N个星系用N-1条虫洞连结起来?
- 输入
- 第一行输入一个整数T,表示測试数据的组数(T<=100)
每组測试数据仅仅有一行。该行仅仅有一个整数N。表示有N个星系。(2<=N<=1000000)
- 输出
- 对于每组測试数据输出一个整数。表示满足题意的修建的方案的个数。
输出结果可能非常大,请输出修建方案数对10003取余之后的结果。
- 例子输入
-
2 3 4
- 例子输出
-
3 16
题目分析:
高速幂+全然图的最小生成树的个数,n个顶点的最小生成树的个数为n^(n-2)。
AC代码1 O(n):
/** *在一个n阶全然图的全部生成树的数量为n的n-2次方 */ #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<cstdlib> #include<cctype> #include<cstring> #include<cmath> #define MOD 10003 using namespace std; int Sum(int n){ int res=n; for(int i=1;i<=n-3;i++){ res*=n; res%=MOD; } return res; } int main() { int n,t; cin>>t; while(t--){ cin>>n; if(n==2){//仅仅有一中 cout<<"1"<<endl; continue; } int res=n; for(int i=1;i<=n-3;i++){ res*=n; res%=MOD; } cout<<res<<endl; } return 0; }AC代码2 O(logn)
/** *在一个n阶全然图的全部生成树的数量为n的n-2次方 */ #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<cstdlib> #include<cctype> #include<cstring> #include<cmath> #define MOD 10003 using namespace std; int Mod(int a,int b)//高速幂 { int ret=1; int tmp=a; while(b) { //奇数存在 if(b&1) ret=ret*tmp%MOD; tmp=tmp*tmp%MOD; b>>=1; } return ret; } int main() { int n,t; cin>>t; while(t--){ cin>>n; if(n==2){//仅仅有一中 cout<<"1"<<endl; continue; } /** int res=n; for(int i=1;i<=n-3;i++){ res*=n; res%=MOD; } cout<<res<<endl; **/ cout<<Mod(n,n-2)<<endl; } return 0; }
NYOJ127 星际之门(一)(最小生成数的个数+高速幂)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。