Jupiter attacks - ICPC Latin America 2011

I have just solved problem Jupiter Attacks! from last year's ICPC Latin America regional contest. You can read the statement here.

Basically there is a sequence of bytes of size L (1 <= L <= 10^5), but not normal bytes, these bytes accept values in the range [0, B-1] (2 <= B <= 10^9). There are N (1 <= N <= 10^5) operations of two possible kinds:

• Change the value of a given position
• Calculate the value of a given interval, considering it a number of B bytes, big-endian. Giving the value modulo P (1 <= P <= 10^9, P prime and given in the input)

So what we need is a efficient way of changing the value of a single byte and calculating the sum of a specified interval, taking linear time to solve this problem is too slow, N*L = 10^10, what is far too much. The limits indicate a logarithmic way of summing seems reasonable.

Well, if this was a simple sum of an interval we would know how to calculate and change the sum in an efficient way, one possible way is using a Binary Indexed Tree (BIT, explanation about this structure at Topcoder), or you might use Segment Tree or a Range Minimum Query.

But we have the problem that the value of a specific cell in the summation depends on the beginning of the interval. But is that such a problem? It is possible to keep the summation with each cell i multiplied by B^(L-i) and divide the summation by the proper value, if we ask for an interval that goes from i to j we have just to divide this sum by B^(L-j) .

Now there is another problem, the values are too big to be kept without taking the modulo and we can't simply divide a value after having applied the modulo. Now comes an important information: P is prime, and as such there is always a modular inverse, which acts as the division operator in modular arithmetics. Modular inverse can be quickly calculated with extended euclidean algorithm.

My implementation to this solution is available at codepad.