從N個城市列表中選擇一個城市/城市的方式

Question

N個城市的編號從1 to N。

任務是選擇從列表中選擇城市/城市的方式的數量。

至少需要選擇1個城市。由於答案可能很大，打印答案模10^9+7

Examples 
Input    Output 
2 (test cases) 
2     3 
1     1 

對於測試案例1：選擇城市的唯一途徑是1，2，1 2 因此答案是3

對於測試用例2：選擇城市的唯一方法是1因此 答案是1

我以下面的方式嘗試（C語言）：

#include<stdio.h> 
#include<math.h> 
const long int REM = 1000000000+7; 
int main() 
{ 
    int t; scanf("%d",&t); while(t--) { 
     long long int n; scanf("%lld",&n); 
     long long int res=1; 
     for(long long int i=0;i<n;i++) { 
      res<<=1; 
      res%=(REM); 
     } 
     printf("%lld\n",res-1); 
    } 
    return 0; 
} 

這是給我超時的時間限制。請建議我更好的performance algorithm。

謝謝

Answer 1

答案是所有可能的子集數（空集除外）其中2^n - 1。

由於2^n會非常大，這就是爲什麼問題要求做模塊化操作，您必須執行Modular Exponentiation來計算2^n。

#include<stdio.h> 
#include<math.h> 

#define MOD 1000000007 

// calculate (b^e) % MOD 
long long powerMod(long long b, long long e) 
{ 
    long long ret = 1; 
    b %= MOD; 
    while(e > 0) 
    { 
     if(e & 1) { 
      ret = (ret * b) % MOD; 
     } 
     b = (b * b) % MOD; 
     e >>= 1; 
    } 
    return ret % MOD; 
} 


int main() 
{ 
    long long tcase, n; 
    scanf("%lld",&tcase); 
    while(tcase--) 
    { 
     scanf("%lld", &n); 
     long long result = powerMod(2, n) - 1; 
     printf("%lld\n", result); 
    } 
    return 0; 
} 

Answer 2

您可以使用二進制指數算法來解決對數時間每個測試用例。