程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NYOJ127 星際之門（一）(最小生成數的個數+快速冪)

NYOJ127 星際之門（一）(最小生成數的個數+快速冪)

編輯：C++入門知識

NYOJ127 星際之門（一）(最小生成數的個數+快速冪)

可以證明，修建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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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<AC代碼2 O(logn) 
 
 
/**
 *在一個n階完全圖的所有生成樹的數量為n的n-2次方
 */
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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<