Hello,
I was trying to solve Codeforces Round #489 (Div. 2), problem: (C) Nastya and a Wardrobe,(http://codeforces.net/contest/992/problem/C), and my solution so far gets the first 21 test cases right.
I know how to solve it, the only problem is outputting correctly using modulo.
My code currently looks like this:
import java.io.*;
import java.util.*;
public class Main {
public static int MOD = (int)Math.pow(10, 9)+7;
public static long powMod(long X,long N){
long result = 1;
X = X % MOD;
while(N > 0){
if(N % 2 == 1)
result = (result * X) % MOD;
N >>= 1;
X = (X*X)%MOD;
}
return result;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long X = in.nextLong();
long K = in.nextLong();
if(X == 1)
System.out.println(powMod(2, K) + 1);
else if(X == 0)
System.out.println(0);
else if(K == 0)
System.out.println(X*2);
else {
long upperLimit = ((X%MOD) * powMod(2, K + 1));
long diff = (X - 1) % MOD;
long lowerLimit = (2*((-diff*((1-powMod(2, K)))) + (X%MOD)))%MOD;
if(X < 1000 && X > 100)
lowerLimit = (2*((-diff*((1-powMod(2, K)))) + (X%MOD)));
if(X > 1000 && K < 1000)
System.out.println((((upperLimit + lowerLimit)%MOD) / 2) % MOD);
else
System.out.println(((upperLimit + lowerLimit) / 2) % MOD);
}
}
}
I've tried several different combinations of modulo addition and multiplication, but none seem to reliably output the answer without me cheating a bit by adding if conditions.
I've seen the rules for modulo arithmetic and multiplication, but following those rules seems to get me even more qrong answers.
I was wondering what exactly am I doing wrong concerning the use of modulo and what to keep in my mind when I encounter similar problems.