# SPOTWO - Editorial

EASY

### PREREQUISITES:

High school maths

### PROBLEM:

Calculate (2N__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 (2N_bin)2 % 1000000007 within time limit. This can be achieved using Right-to-left binary method for modular exponentiation.
See mugurelionutâ€™s solution for simple implementation in C/C++

Another simple way of calculating 2n 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
Testerâ€™s solution can be found here and here

4 Likes

if power is greater than MOD valueâ€¦ you could use this to simplify the result calculation,

(x^(N%(MOD-1)))%MOD,

Eg, Binary Representation of 600000 in decimal is 10010010011111000000,
now 10010010011111000000 % ((1e9+7)-1) = 50940294

You can now see that (2^50940294)(1e9+7) = (2^10010010011111000000)(1e9+7) = 140171955.
Simple DP should take care about the rest of the optimizations.

4 Likes

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 grade-school arithmetic scheme to â€śget aroundâ€ť the â€śsupposedâ€ť ULL overflow.

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:

2M-1 mod M = 1, where M = 109+7.

Therefore, we just output 2(2*N_bin % (M-1)) 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 {20 mod M, 22 mod M, 22 mod M,â€¦, 2k 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:

``````#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define M 1000000007
#define ll long long

ll pw(ll a,ll b, ll md){
ll r;
if(!b) return 1;
r = pw(a,b/2,md);
r = (r*r)%md;
if(b%2) r = (r*a)%md;
return r;
}

int main(){
int T, N;
int B;

scanf("%d",&T);
while(T--){
scanf("%d",&N);
B = 0;
p = 0; add = 1;
while(N){
N /= 2;
}
p = (p*2)%(M-1);
printf("%d\n",(int)pw(2,p,M));
}

return 0;
}
``````

This was the reason why the problem was set as EASY instead of MEDIUM.

Nontheless, I hope you have enjoyed it

Best,

Bruno

2 Likes

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?

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.

• (2^10)%M
• (2^100)%M
• (2^1000)%M
• (2^10000)%M
• .
• .
• .
• (2^10000000000000000000)%M

Now,600000â€™s binary (2^10010010011111000000)%M
can be written as *((2^10000000000000000000)%M)*(2^(10000000000000000)%M)â€¦ (2^1000000)%M)%M

5 Likes

this is only possible when MOD is prime.

Yeah. . My solution exploited Fermatâ€™s little theorem too

this is what i didâ€¦it is definitely the most simple and fast way.
http://www.codechef.com/viewsolution/2923042

Yeah but then again, most likely the MOD is selected to be a prime number to get the most out of it !!

same hereâ€¦http://www.codechef.com/viewsolution/2980062 simple and efficient

I implemented a Dynamic Programming approach. Each problem can be divided into 2 sub-problems (except powers of 2 like 4, 8, 16, 32, â€¦ which can be trivially solved). See below:

Base cases:

• 2^1 = 2^1 = 2;
• 2^2 = 2^10 = 1024;

• 2^3 = 2^11 = 2^10 * 2^1;
• 2^4 = 2^100 = (2^10)^10;
• 2^5 = 2^101 = 2^100 * 2^1;
• 2^6 = 2^110 = 2^100 * 2^10;
• â€¦
• â€¦
• 2^168 = 2^10101000 = 2^10100000 * 2^1000
• â€¦
• and so on

Execution time - 0.23 Seconds

http://www.codechef.com/viewsolution/2913164

Why no correct submission in python ?

Can anyone tell me why this gave me WA?
http://www.codechef.com/viewsolution/2968557

@anil09

u can see my version of solutionâ€¦
hope u get wat i mean in the codeâ€¦

http://www.codechef.com/viewplaintext/2919571

I guess directly using ULL wonÂ´t work and you have to do it incremetallyâ€¦ Check @mugurelionutâ€™s solution for further reference

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.