WA in MYSARA

help
,
1

Problem Code: MYSARA

problem: https://www.codechef.com/problems/MYSARA
here’s my program: https://www.codechef.com/viewsolution/30749301

2

I guess pow function can result in values much greater than long long int, so u need to implement a power function that mod values as well each time u multiply the values by 2.

Much like https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/
Thank you

3

Anyway, thanks for help.

4

Your power function is still wrong. It will overflow. You need to take %p at each step.

const ll p=1e9 + 7;
//rest of code
ll power( ll N, ll S ){
    if( S < 0 ){
        return 0;
    }
    ll result = 1;
    while( S > 0 ){
        if( S & 1 ){
            result = result * N;
            result%=p;
        }
        N *= N;
        N%=p;
        S >>= 1;
    }
    return result;
}

Then it will work.

5

https://www.codechef.com/viewsolution/30753465

error in power function : take mod with both result and N variable

when you set count = -1 then continue from there because if you don’t continue
count += __builtin_popcount(last); can make it non negative

6

Yes it worked. I noticed it in other’s coude too, but couldn’t understand it.

Can you please explain why is it necessary to mod it down at every step?
Also, thanks for hellp. :smile:

7

Anything above 2^64 will overflow. So if count was 70, you would be computing 2^70 which will most definitely overflow before you take %p. So to avoid that, we just take mod p at every step.

1 Like
8

I understood. Thank you for all your efforts. You also helped my friend a few days ago. We’re new at competitive programming. Thanks to everyones’s support. :pray: