c++ - 从 N 个城市的列表中选择一个或多个城市的方法数

Question

有一个 N 个城市的列表，编号从 1 到 N。

任务是选择从列表中选择城市的方式数量。

必须至少选择 1 个城市。由于答案可能很大，打印答案模 10^9+7

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

For test case 1: The only ways to select the cities is 1, 2 ,1 2 Therefore the answer is 3.

For test case 2: The only way to select a city is 1 Therefore the answer is 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;
}

这让我超出了时间限制。请建议我一个更好的性能算法。

谢谢

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;
}