N都市のリストから都市/都市を選択する方法の数

Question

N都市のリストは、1 to Nから番号が付けられています。

このタスクは、都市/都市をリストから選択する方法の数を選択することです。

少なくとも1つの都市を選択する必要があります。答えは大きくすることができるように、テストケース1について回答モジュロ10^9+7

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

を印刷：都市を選択するための唯一の方法1、2、1 2 したがって答えは3

でありますテストケース2の場合

：都市を選択する唯一の方法は、したがって 答えは私は次のようにしようとした1

（C言語）で1：

#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は非常に大きくなります。そのため、問題がモジュール式操作を行うよう求められた場合、2^nを計算するにはModular Exponentiationを実行する必要があります。

#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

あなたは対数時間で各テストケースを解決するために、バイナリ累乗アルゴリズムを使用することができますありがとうございました。