PROBLEM LINK:DIFFICULTY:EASY PREREQUISITES:High school maths PROBLEM:Calculate (2^{N__bin})^{2} % 1000000007 for given N, where N__bin stands for the decimal number encoded by the representation in base 2 of the number N QUICK EXPLANATION:Store the binary representation of N as decimal number in appropriate data type(as per language). Use fast exponentiation technique to calculate the result within time limit. EXPLANATION:First task is to get binary representation of N as decimal number. The largest value of N is 600000 whose binary representation is 10010010011111000000 which is less than 2^64 but greater than 2^63. For C programmers, unsigned long long is suitable to store this value. Next task is to calculate (2^{N_bin})^{2} % 1000000007 within time limit. This can be achieved using Righttoleft binary method for modular exponentiation. See mugurelionut’s solution for simple implementation in C/C++ Another simple way of calculating 2^{n} in log n time is by using exponentiation by squaring. See setter’s solution for a simple function using this technique. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here
This question is marked "community wiki".
asked 11 Nov '13, 15:04
showing 5 of 7
show all

This is what I did 600000's binary is 10010010011111000000. So I computed an array of following values offline using a C program of modular exponentiation.
Now,600000's binary (2^10010010011111000000)%M can be written as ((2^10000000000000000000)%M)(2^(10000000000000000)%M)..... (2^1000000)%M)%M answered 11 Nov '13, 16:54
this is what i did...it is definitely the most simple and fast way. http://www.codechef.com/viewsolution/2923042
(11 Nov '13, 17:19)
same here..http://www.codechef.com/viewsolution/2980062 simple and efficient
(12 Nov '13, 01:07)

Hello @all, Besides the presented solutions (the tester one and mine) there is a much more clever solution of which I was not aware of. Sadly, my solution was too complicated, possibly because I wanted to make something look harder than what it actually was. I thought that for a specific value of N (around 527.000) its binary representation would exceed the capacity of an unsigned long long and as such I used simple fast exponentiation below that "threshold" value and devised a simple gradeschool arithmetic scheme to "get around" the "supposed" ULL overflow. You can read it when the links are live :) The testers' solution uses @mugurelionut scheme where the fact of not occuring any overflow just makes the task trivial with simple fast exponentiation (I really must have overlooked this fact while searching for C++ type limits). Finally, the more theoretical solution which possibly lots of contestants used is based on a variation of Fermat's Little Theorem that exploits the fact that: 2^{M1} mod M = 1, where M = 10^{9}+7. Therefore, we just output 2^{(2*N_bin % (M1))} mod M and we have correct answer!! As you can see, this trick would allow for a much higher constraint on the value of N assuming you would process it properly. Sadly, when I was told about this trick, I didn't fully understood it (it was few months ago) and I ended up writing the most naive solution possible. Hiroto Sekkido told me that even if M is changed, the sequence {2^{0} mod M, 2^{2} mod M, 2^{2} mod M,..., 2^{k} mod M, ...} must be periodic (ignoring the first a few terms), so such kind of cheat could be applicable. I can leave here his solution using this approach as reference:
This was the reason why the problem was set as EASY instead of MEDIUM. Nontheless, I hope you have enjoyed it :) Best, Bruno answered 11 Nov '13, 16:10

Yeah. . My solution exploited Fermat's little theorem too :) answered 11 Nov '13, 17:07

I implemented a Dynamic Programming approach. Each problem can be divided into 2 subproblems (except powers of 2 like 4, 8, 16, 32, ... which can be trivially solved). See below: Base cases:
Execution time  0.23 Seconds answered 12 Nov '13, 10:13

Can anyone tell me why this gave me WA? http://www.codechef.com/viewsolution/2968557 answered 12 Nov '13, 20:20
I guess directly using ULL won´t work and you have to do it incremetally... Check @mugurelionut's solution for further reference
(12 Nov '13, 21:10)
Your solution is giving WA because you are passing 2nbin to your function. 600000 in binary is close to 1.1E19 and range of ULL is 1.8E19. So 2nbin will go out of range. What you can do is make two calls to the modular exponent function, first to calculate 2^nbin and then (result of first call)^2.
(13 Nov '13, 05:17)

class Codechef { public static void main (String[] args) throws java.lang.Exception { Scanner sc=new Scanner(System.in); int t=sc.nextInt(); while(t>0) { int n=sc.nextInt();
int val=Integer.parseInt(s);
System.out.println(ans);} // your code goes here } } answered 04 Mar '15, 02:47

solution links not live..
how can we solve the same problem if N > 600000 i.e, if binary representation has more than 64 bits?
@anil09, use big integer in the case of java, or use strings to manipulate bigger digits..
@mecodesta: suppose i am using only C. and i have 100bit value stored in string.That 100bit value treated as integer(N_bin) according to problem. How can we do left/right shift operations on that string?
Solution links updated
Why no correct submission in python ?
@anil09
u can see my version of solution... hope u get wat i mean in the code.. :)
http://www.codechef.com/viewplaintext/2919571