Key Set

http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1011&cid=594

Key Set

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

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

 

直接输出2的n-1次方-1？当然2的10的9次方的次方肯定很大，然而结果只是对其求余与1000000007，所以快速幂，对每次都求余，就不会超出类型啦

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL mod = 1000000007;
LL Pow (LL x, LL y)
{
    LL ans = 1;
    while (y)
    {
        if (y % 2)
            ans = ans * x % mod;
        x = x * x % mod;
        y /= 2;
    }
    return ans;
}
int main ()
{
    LL t, n;
    scanf ("%lld", &t);
    while (t --)
    {
        scanf ("%lld", &n);
        LL ans = Pow (2, n-1);
        printf ("%lld
", ans-1);
    }
    return 0;
}