2015 多校联赛 ——HDU5363（快速幂）-白红宇

2015 多校联赛 ——HDU5363（快速幂）

阅读量：6258 次

发布时间：2019-06-22

本文共 1416 字，大约阅读时间需要 4 分钟。

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

(1≤T≤105), indicating the number of test cases. For each test case:

The first line contains an integer

(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 

给你一个1-n的集合，问你有多少个子集的元素和为偶数

假设偶数有a个，奇数有b个,总数为n：

偶：C（0, a）+ C（1 , a）....... + C（a, a） = 2 ^ a

奇：C（0, b）+ C（2 , b）....... + C（b, b） = 2 ^ (b - 1)

all = 偶 * 奇 - 1（奇偶中都不选的情况）；

---> all = 2 ^ (a + b - 1)- 1 = 2 ^ (n - 1) -1

#include 
     
      #include 
      
       #include 
       
        #pragma comment(linker, "/STACK:102400000,102400000")using namespace std;typedef long long ll;char ma[1100][1100];int ln, lm;const int mod = 1000000007;ll pow_mod(int a,int n){    if(n == 0)        return 1;    ll x = pow_mod(a,n/2);    ll ans = (ll)x*x%mod;    if(n %2 == 1)        ans = ans *a % mod;    return ans;}int main(){    int T;    scanf("%d",&T);    while(T--)    {        int n;        scanf("%d",&n);        ll sum1 = (pow_mod(2,n-1)-1)%mod;        printf("%I64d\n",sum1);    }    return 0;}