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
1
2
3
4
Sample Output
0
1
3
7
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<cstdio>
#include<cstring> using namespace std; #define ll long long const int mod=1e9+; ll quick_pow(ll n)
{
ll ret=;
ll x=;
while(n){
if(n&)
ret=ret*x%mod;
x=x*x%mod;
n>>=;
}
return ret;
} int main()
{
int test;
scanf("%d",&test); while(test--){
ll n;
scanf("%I64d",&n);
printf("%I64d\n",quick_pow(n-)-);
}
return ;
}