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
?
?
?
?