Key Set

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 2757    Accepted Submission(s): 1380

  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   问题链接：HDU5363 Key Set 问题描述：（略） 问题分析：   可以根据组合计算推导出f(n)=2^(n-1)-1。使用快速模幂计算即可。 程序说明：（略） 参考链接：（略） 题记：（略）   AC的C++语言程序如下： /* HDU5363 Key Set */ #include using namespace std; typedef long long LL; const LL MOD = 1000000007; // 快速模幂 LL powmod(LL x, LL n, LL m) { LL result = 1; for(; n; n>>=1) { if(n & 1) { result *= x; result %= m; } x *= x; x %= m; } return result; } int main() { int t; scanf("%d", &t); while(t--) { LL n; scanf("%lld", &n); printf("%lld ", powmod(2, n- 1, MOD) - 1); } return 0; }