A Chocolate Fiesta

A Chocolate Fiesta

Problem Statement

Welcome to the exciting class of Professor Manasa. In each lecture she used to play some game while teaching a new concept. Today's topic is Set Theory. For today's game, she had given a set A = {a1, a2, ...aN} of N integers to her students and asked them to play the game as follows.

At each step of the game she calls a random student and asks him/her to select a non-empty subset from set A such that this subset had not been selected earlier and the sum of subset should be even. This game ends when all possible subsets had been selected. Manasa needs your help in counting the total number of times students can be called assuming each student gives the right answer. While it is given that if two numbers are same in the given set, they have different colors. It means that if a1 = a2, then choosing a1 and choosing a2 will be considered as different sets.

Note

1. Two subsets are different if there exists an element (ak) that is present in one subset but not in other. Let's say set A = {a1, a2, a3} = {2, 2, 3}, then all possible subsets are {}, {a1}, {a2}, {a3}, {a1, a2}, {a1, a3}, {a2, a3}, {a1, a2, a3} which is equivalent to {}, {2}, {2}, {3}, {2, 2}, {2, 3}, {2, 3}, {2, 2, 3}.
2. Students can be called multiple times.

Input Format
The first line contains an integer N i.e. size of set A.
Next line will contain N integers, each representing an element of A.

Output Format
Print number of time students are called. As this number can be very large you have to print the answer modulo (109 + 7).

Constraints
1 ≤ N ≤ 105
0 ≤ ai ≤ 104 , where i ∈ [1 .. N]

Sample Input 00

4
2 4 6 1

Sample Output 00

7

Sample Input 01

3
1 2 2

Sample Output 01

3

Explanation
There are 7 different ways in which a non-empty subset, with even sum, can be selected, i.e.,{2}, {4}, {6}, {2, 4}, {2, 6}, {4, 6}, {2, 4, 6}.

For second sample test case, there are 3 different ways in which a non-empty subset, with even sum, can be selected, i.e., {a2}, {a3}, {a2, a3} which is equivalent to {2}, {2}, {2,2}.

---------------------------------------editorial-----------------------------

Case 1: Number of odd numbers in given set = 0
So, we can choose one of more elements in 2number of element - 1 number of ways and sum of elements in each set will be even.

Case 1: Number of odd numbers in given set > 0 

Now the sum of the elements in any subset S can be odd only when the count of odd numbers in the subset is odd.
Let n_odd represents the number of odd numbers in the set S and n_even denote the number of even numbers.
The possible ways of choosing odd number of odd numbers from n_odd :
n_oddC1 +n_oddC3 +n_odd Cn_odd
The total number of possible subsets formed with odd count of odd numbers = 2^(n_odd-1) * ( 2^ n_even) [ since we can have as many even numbers as we want without changing the sum from odd to even , and all possible subsets = 2^n_even]

Approach 2 by Kevin

Assume first that the empty set is a valid subset (we'll remove it later). If there are no odd elements in the set, then the answer is 2^n. If there is at least one odd element, let x be the last odd element. Choose a subset among the n-1 remaining values. If the sum is odd, then include x. Otherwise, don't include x. This way, the subset we choose always has an even sum. Thus the answer is 2^(n-1).

In other words, the number of nonempty subsets whose sum is even is 2(n-k) - 1 where k = 1 if there's an odd element, otherwise 0.

print(pow(2,input()-any(int(x)&1 for x in raw_input().strip().split()),10**9+7)-1)%(10**9+7)

 Tested by shashank21j

Problem Tester's code :

n=input()
assert n<=10**5 and n>=1
mod = 10**9 + 7
arr = [int(x) for x in raw_input().split()]
for i in arr:
  assert i <=10**4 and i >= 0
odd = filter(lambda x:x%2==1, arr)
even = len(arr) - len(odd)
if len(odd)==0:
  print (pow(2,even,mod)-1)%mod
else:
  print (pow(2,len(arr)-1,mod)-1)%mod




----------------------------------------------code---------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

typedef long int li;

#define test()    int test_case;cin>>test_case;while(test_case--)

#define fr(i,n) for(int i=0;i<n;i++)

#define frr(i,a,n) for(int p=i;p<n;p++)

#define sll(a) scanf("%lld",&a)

#define sl(a) scanf("%ld",&a)

#define si(a) scanf("%i",&a)

#define sd(a)  scanf("%ld",&a)

#define sf(a) scanf("%f",&a)

#define rn(a) return a

#define pai pair<int,int>

#define pal pair<li,li>

#define pall pair<lli,lli>

#define ff first

#define ss second

#define mod  1000000007

#define mp make_pair

#define pb push_back

#define pll(a) printf("%lld\n",a);

#define pl(a) printf("%lld\n",a);

#define pi(a) printf("%d\n",a);

#define pd(a) printf("%lf\n",a);

#define pf(a) printf("%f\n",a);

lli power(lli x,lli y)

{

    lli  temp;

    if( y == 0)

        return 1;

    temp = power(x, y/2);

    if (y%2 == 0)

        return (temp%mod*temp%mod)%mod;

    else

        return ((x*temp)%mod*temp)%mod;

}

int main()

{

lli  n;

 sll(n);

 lli eve=0;

 lli odd=0;

 fr(i,n)

  {

  lli a;

  cin>>a;

  if(a%2==0) eve++;

  if(a%2==1) odd++;

   

  }

 

 lli even=  power(2,eve)-1;

 if(odd==0)

  {

  pll(even);

  return 0;

  }

 lli od=power(2,odd-1);

//  cout<<od<<endl;

 lli ode=power(2,odd)-1;

 // cout<<ode<<endl;

 lli temp=ode-od;

 if(temp<0) temp+=mod;

//  cout<<" odd "<<temp<<" eve "<<even<<endl;

 //  cout<<even+temp+even*temp;

 lli ans=((even+temp)%mod+(even*temp)%mod)%mod;

pll(ans);

    

  

  return 0;

}