题目描述:
http://acm.nyist.net/JudgeOnline/problem.php?pid=127
现在,问题来了,皇帝想知道有多少种修建方案可以把这N个星系用N-1条虫洞连结起来?
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; }
原文:http://blog.csdn.net/fool_ran/article/details/42065701