从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

您可以使用二进制指数算法来解决对数时间每个测试用例。