题目链接：https://cn.vjudge.net/contest/226118#problem/K
这题应该说是思维题，一开始了很久都没有想出来，后来听别人一说，就明白了。 题目中说了对于集合n，其中的元素为 [ 1, 2, 3 … n ] 所以这个集合的非空子集个数就是 2^n - 1 所以接下来我们这么来想，我们把集合n中的 1 这个元素去掉，就还剩下n-1个元素，这n-1个元素可以组成非空集合的个数就是2^(n-1) - 1，这其中有和为偶数的也有和为奇数的，对于和为偶数的子集合，我们可以直接算入答案，对于和为奇数的子集合，我们可以给它加上 1 这个元素让其变为和为偶数，这样一来原本和为奇数的子集合也就可以直接算入答案了，所以这 2^(n-1) - 1个子集合就都是答案。 分析就到这，接下来，由于n较大，达到了10^9所以我们可以是用快速幂取模来实现，这样会快很多。 代码如下：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> #include <set> #include <map> #include <queue> #include <string> #include <stack> using namespace std; typedef long long LL; typedef unsigned long long uLL; const LL MOD = 1000000007; LL quick_pow(LL a, LL b){ LL ans = 1; while(b){ if(b & 1) ans = ans*a%MOD; a = a*a%MOD; b >>= 1; } return ans; } int main(){ int T; scanf("%d", &T); while(T--){ LL n; scanf("%lld", &n); printf("%lld\n", quick_pow(2, n-1)-1); } return 0; }