hdu 5363 Key Set （高速幂取模）

题意：

给你一个元素为1到n的集合，让你求有多少个非空子集，子集内的元素之和为偶数。

解析：

子集中满足元素之和为偶数那么得满足几何中的奇数必须为偶数个。
那么偶数的情况可以任意取。一个几何中有 $n/2$ 个偶数，有 $(n+1)/2$个奇数。
那么最终的结果为$\sum_{i=1}^{n/2}{C_{n/2}^i}*\sum_{j=1}^{(n+1)/2}C_{(n+1)/2}^j = 2^{n-1}-1$
由于结果比较大，所以要用到快速幂取摸。

$my$$code$

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
int n;

ll modpow(ll a, ll k) {
    ll c = 1;
    while(k) {
        if(k & 1) c = (c*a) % MOD;
        a = (a*a) % MOD;
        k >>= 1;
    }
    return c;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        printf("%lld\n", modpow(2, n-1) - 1);
    }
    return 0;
}