leonz - 6 months ago 35

Java Question

I'm writing a program for my competitive programming class's homework and I can't get over one problem. This problem requires you to calculate all permutations of a certain string based on certain condition and my program does that. However, the problem is when the input is a really large string, it can be up to 10^6.

Solution to the problem is 2^result, where result depends on length of input string, so for 10^6 it can be up to 5*10^5. Solution must be given in form of: result % (10^9 + 7).

I've tried putting solution into a BigInteger, it runs out of heap space. I've tried working with doubles, it overflows. Is there something I'm missing or is there a way to deal with this? Thank you.

Here are some attempts:

`System.out.println((int) (Math.pow(2, counter) % (1e9 + 7)));`

//it prints out 0, probably due to overflow?

DecimalFormat df = new DecimalFormat("#");

System.out.println(df.format(Math.pow(2, counter) % (1e9 + 7)));

//prints out �

Answer

You don't need to handle enormously large numbers to do this.

The assignment intends for you to implement modular exponentiation. BigInteger already implements it as modPow. It allows you to calculate `(b^e) % c`

without having to deal with numbers significantly larger than `c`

.

Here's Wikipedia's pseudo-code for remainder after exponentiation through repeated squaring:

```
function modular_pow(base, exponent, modulus)
if modulus = 1 then return 0
Assert :: (modulus - 1) * (modulus - 1) does not overflow base
result := 1
base := base mod modulus
while exponent > 0
if (exponent mod 2 == 1):
result := (result * base) mod modulus
exponent := exponent >> 1
base := (base * base) mod modulus
return result
```