Time Limit: 2000/1000 MS (Java/Others)  

Memory Limit: 131072/131072 K (Java/Others)

Problem Description

soda has a set S with n integers {

1,2,…,n}. A set is called key set if the sum of integers in the set is an even number. He wants to know how many nonempty subsets of S are key set.

 

 

Input

There are multiple test cases. The first line of input contains an integer T (1≤T≤105), indicating the number of test cases. For each test case:

The first line contains an integer n (1≤n≤109), the number of integers in the set.

 

 

Output

For each test case, output the number of key sets modulo 1000000007.

 

 

Sample Input

4 1 2 3 4

 

 

Sample Output

0 1 3 7

 

 

Author

zimpha@zju

 

 

Source

 

 

 

 

 

 

 

 

题意：给出一个数n，则有一个集合set={1,2,3,4,...,n}

问这个集合set有多少个非空子集，使得子集里面所有元素的和为偶数

 

我们知道(a+b)^n=C(n,0)a^0*b^n...

令a=b=1,得：2^n=C(n,0)+C(n,1)+C(n,2)+...+C(n,n-1)+C(n,n)

令a=1,b=-1,得：0=C(n,0)-C(n,1)+C(n,2)-C(n,3)+...-C(n,n-1)+C(n,n)

则有：C(n,0)+C(n,2)+..+C(n,n)=C(n,1)+C(n,3)+...+C(n,n-1)=2^(n-1)

 

 

对于给出的m，

当m=2*n时，有n个偶数，n个奇数，偶数可以选择0,1,2,3个等，奇数可以选择0,2,4,6个等

写出组合式，化简得：ans=2^(m-1)-1

-1是因为要减去空集的情况

当m=2*n-1时，同样化简可得：ans=2^(m-1)-1

 

则：ans=2^(m-1)-1

利用快速幂即可求。

 

 

 

#include
      
       #include
       
        using namespace std;#define ll long longconst int mod=1e9+7;ll quick_pow(ll n){    ll ret=1;    ll x=2;    while(n){        if(n&1)            ret=ret*x%mod;        x=x*x%mod;        n>>=1;    }    return ret;}int main(){    int test;    scanf("%d",&test);    while(test--){        ll n;        scanf("%I64d",&n);        printf("%I64d\n",quick_pow(n-1)-1);    }    return 0;}