General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
19143565 Practice:
bluemmb
697E - 10 GNU C++11 Accepted 624 ms 876 KB 2016-07-15 08:42:13 2016-07-15 08:42:13
 
 
→ Source
#include <bits/stdc++.h>
typedef long long int lli;

using namespace std;

/*

one can reach this recurrence  : p(i) = 1/2 * ( 1 - p(i-1) ) , after solving it , we get something like these :  

n = 1 -> 1

n = 2 -> 0								--> ( 2^0 ) / 2^1

n = 3 -> 1/2 * ( 1 )					--> ( 2^1 + 1 ) / 2^2

n = 4 -> 1/2 * ( 1 - 1/2 )				--> ( 2^2 + 2^0 ) / 2^3

n = 5 -> 1/2 * ( 1 - 1/2 + 1/4 )		--> ( 2^3 + 2^1 + 1 ) / 2^4

n = 6 -> 1/2 * ( 1 - 1/2 + 1/4 - 1/8 )	--> ( 2^4 + 2^2 + 2^0 ) / 2^5

....

denominator power is always n-1;

separate numbers into two groups by (n-1)%2, then solve geometric sequencec for nominators of them ,
you will reach to these formulas :

odds  -> ( 2 * ( 2^(n-2) - 1 ) / 3 ) + 1

evens -> ( 2^(n-1) - 1 ) / 3

*/

const lli M = 1e9 + 7;
const lli Inv2 = 500000004;
const lli Inv3 = 333333336;

lli Pow( lli x , lli p )
{
	if ( p == 0 ) return 1;
	if ( p == 1 ) return x % M;
	
	lli r = Pow( x , p/2 );
	r = (r*r) % M;
	
	return (r * Pow(x , p%2)) % M;
}

int main() 
{
	lli k; cin>>k;
	lli a[112345];
	
	lli x = 2;
	lli z = 1;			// odd or even ?
	for ( int i=1 ; i<=k ; i++ )
	{
		cin>>a[i];
		z = (z) & (a[i]%2);
		x = Pow( x , a[i] ) % M;
	}
	
	z ^= 1;				// n-1 !
	if ( z == 0 )
	{
		x = (x * Inv2) % M;
		
		lli m = x;
		lli s = (((x - 1 + M) % M) * Inv3)%M;
		
		cout<<s<<"/"<<m<<"\n";
	}
	else
	{
		x = ( x * Inv2 ) % M;
		
		lli m = x;
		lli s = ( x * Inv2 ) % M;
		s = ( s - 1 + M ) % M;
		s = ( s * 2 ) % M;
		s = ( s * Inv3 ) % M;
		s = ( s + 1 ) % M;
		
		cout<<s<<"/"<<m<<"\n";
	}
	
	return 0;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details