NYOJ127 星际之门（一）(最小生成数的个数+快速幂) -电脑资料

电脑资料时间：2019-01-01 我要投稿

【www.unjs.com - 电脑资料】

可以证明，修建N-1条虫洞就可以把这N个星系连结起来，

NYOJ127 星际之门（一）(最小生成数的个数+快速幂)

。

现在，问题来了，皇帝想知道有多少种修建方案可以把这N个星系用N-1条虫洞连结起来？

输入第一行输入一个整数T,表示测试数据的组数(T<=100)

每组测试数据只有一行，该行只有一个整数N，表示有N个星系。(2<=N<=1000000)

输出对于每组测试数据输出一个整数，表示满足题意的修建的方案的个数。输出结果可能很大，请输出修建方案数对10003取余之后的结果。样例输入

样例输出

题目分析：

快速幂+完全图的最小生成树的个数，n个顶点的最小生成树的个数为n^(n-2)。

AC代码1 O(n)：

/** *在一个n阶完全图的所有生成树的数量为n的n-2次方 */#include#include#include#include#include#include#include#include#include#include#include#include#include#define MOD 10003using 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<AC代码2 O(logn)
/** *在一个n阶完全图的所有生成树的数量为n的n-2次方 */#include#include#include#include#include#include#include#include#include#include#include#include#include#define MOD 10003using 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<

相关文章