0

I am solving a problem which requires me to calculate the sum of squares of all possible subsets of a set. I am required to return this sum, modulo 10^9+7

I have understood the logic. I just need to sum the squares and multiply the result by 2^N-1, where N is the size of the set.

But the issue is that N can be as big as 10^5. And for this, I am getting an integer overflow. I looked into fast modular exponentiation but still where would I store something as huge as 2^100000 ? Can I use the modulo as I calculate the power of 2, to keep the number down? Wouldn't that change the final value?

If anyone can tell me how to get it or what to read into, it would be really helpful.

Karan Singh
  • 1,114
  • 1
  • 13
  • 30
  • 1
    why do you need to store something big as 2^100000 ? why do you even need to store something bigger than 10^9+7? – nivpeled Jul 28 '19 at 07:45
  • See `boost::multiprecision`. – seccpur Jul 28 '19 at 07:54
  • 2
    `(2^N-1)%(10^9 + 7)` only needs to be calculated once. Then use the identity `(a * b)%c == ((a % c) * (b % c))%c`. You'll probably need to do a similar thing to avoid overflow when computing the sum of squares (modulo 10^9 + 7) anyway. – Peter Jul 28 '19 at 08:00
  • [power by squaring](https://stackoverflow.com/a/30962495/2521214) computed in modulo directly will not overflow ... see [modpow in here](https://stackoverflow.com/q/18577076/2521214) its done in modulo `p` arithmetics of the NTT class – Spektre Jul 28 '19 at 08:29
  • Use a bignum library (like [GMP](https://gmplib.org/) for example). – Jesper Juhl Jul 28 '19 at 09:47
  • @JesperJuhl you don't need any big int solution to solve this. Just a simple `int32_t` is enough to get the result modulo 10^9+7. [How to compute a^b^c mod p?](https://stackoverflow.com/q/46944581/995714), [How to calculate modulus of large numbers?](https://stackoverflow.com/q/2177781/995714) – phuclv Jul 28 '19 at 10:09
  • Possible duplicate of [To Find Large Powers in C++](https://stackoverflow.com/questions/20027271/to-find-large-powers-in-c) – phuclv Jul 28 '19 at 10:09
  • @seccpur you need [modular exponentiation](https://en.wikipedia.org/wiki/Modular_exponentiation) instead of a multiprecision library for this – phuclv Jul 28 '19 at 10:11

1 Answers1

0

If you modulo some value with 2^something_big it just means that you don't have to output bits beyond something_big. For instance x%power(2,10) == x%(1<<10) == x&(1<<10 - 1) == x&1023.

So in your case, the problem is computing the actual value before the modulo while keeping in mind that you only need 99999 bits. All higher bits are to be dropped (and should not influence the result if I understand your premise correctly).

Btw. storing 99999 bits is doable. It's just 13kB.

bitmask
  • 32,434
  • 14
  • 99
  • 159