题目链接:
题目大意:
给出一个到n的自然数集合,问它有多少个子集,元素之和是偶数。
题目分析:
- 首先偶数不会导致集合的和的奇偶性发生变化;奇数会导致集合的和的奇偶性发生变化。我们设奇数m1个,偶数m2个。
- 所以我们可以选取0~m1个偶数,但是只能选取偶数个奇数。
- 那么偶数的方案数就是 ∑i=0m1Cim1=(1+1)n=2m1
- 那么奇数的方案数就是 ∑i=0且i是偶数m2Cim2=(1+1)n−(1−1)n2=2n−1
AC代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL mod = 1000000007;
int n,t;
LL pow1 ( LL num , LL n )
{
LL ret = 1;
while ( n )
{
if ( n&1 )
{
ret *= num;
ret %= mod;
}
num = num*num;
num %= mod;
n >>= 1;
}
return ret;
}
int main ( )
{
scanf ( "%d" , &t );
while ( t-- )
{
scanf ( "%d" , &n );
LL ans = pow1 ( 2 , n-1 );
cout << (ans-1+mod)%mod << endl;
}
}