首页 > 代码库 > 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个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。