程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> NYOJ127 星際之門(一)(最小生成數的個數+快速冪)

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

編輯:關於C++

 

可以證明,修建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<

 

 
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved