Hackerrank - A Chocolate Fiesta

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}.

Solution:

1. #include <bits/stdc++.h>
2. #define pb push_back
3. using namespace std;
4. typedef long long LL;
5. const int S = 100003;
6. const int MOD = 1e9+7;
7. const double pi = 2 * acos( 0.0 );
8.  
9. inline int _Int(){ int x; scanf( "%d", &x ); return x; }
10. inline LL _LLi(){ LL x; scanf( "%lld", &x ); return x; }
11. void pruts(){ puts( "-1" ); exit( EXIT_SUCCESS ); }
12.  
13. int dirX[] = { 1, 0, -1, 0, 1, -1, 1, -1 };
14. int dirY[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
15. int rX[] = { 1, 1, 2, 2, -1, -1, -2, -2 };
16. int rY[] = { 2, -2, 1, -1, 2, -2, 1, -1 };
17.  
18. template < class T > T tri_Area( T x1, T y1, T x2, T y2, T x3, T y3 ){ return abs( x1*( y2-y3 ) - y1*( x2-x3 ) + ( x2*y3-x3*y2 ) );};
19. template < class T > T Distance( T x1, T y1, T x2, T y2 ){ return sqrt( ( x1-x2 ) * ( x1-x2 ) + ( y1-y2 ) * ( y1-y2 ) ); };
20. template < class T > T bigMod( T n, T p, T m ){ if( p == 0 )return 1; if( p&1 )return ( n*bigMod( n, p-1, m ) )%m; T x = bigMod( n, p/2, m ); return ( x*x )%m; };
21.  
22. int sset(int N, int pos){return N=N|(1<<pos);}
23. bool check(int N, int pos){return (bool)(N&(1<<pos));}
24. int reset(int N, int pos){return N=N&~(1<<pos);}
25. /*******************###########################################********************
26. ********************##   MD. YA-SEEN ARAFAT(ThunderStroke)   ##********************
27. ********************##    CSE, University of Asia Pacific    ##********************
28. ********************###########################################********************/
29.  
30. LL dp[ 100000+2 ][ 3 ];
31. int A[ 100000+2 ], n;
32.  
33. LL chocolate( int ind, int sum ){
34.     if( ind == n )return ( !sum );
35.     LL &add = dp[ ind ][ sum ];
36.     if( add != -1 )return add;
37.     add = chocolate( ind + 1, sum ) % MOD + chocolate( ind+1, ( sum+A[ind] )&1 );
38.     return add % MOD;
39. }
40.  
41. void Love(){
42.     memset( dp, -1, sizeof( dp ) );
43.     n = _Int();
44.     for( int i = 0; i < n; i++ )A[ i ] = _Int();
45.     printf( "%lld\n", chocolate( 0, 0 )-1 );
46. }
47.  
48. int main(){
49.     #ifndef ONLINE_JUDGE
50. //        freopen("in.txt", "r", stdin);
51. //        freopen("n.txt", "w", stdout);
52.     #endif
53.     Love();
54.     return 0;
55. }