Is it possible to use somehow that p is prime?
My AC solution doesn't use this fact, but I'm wondering is there a simpler way to solve this task.

Complexity is (M + N) * log N, where N is a size of the array and M is a number of queries

I needed primality of 'p' when I calculated S(K) from sums of powers for Ai. I needed to divide by 2, 6 or 24 in the end. Primality plays important role when you find inverse of these divisors modulo 'p'. Also the fact that S>1000 was also convenient fact because some multiplications would turn to zero for quite small p.

This problem is named "Elementary Symmetric Functions".
There is formula (by Newton) that gives relation between elementary symmetric polynomials and "power sums" (that are symmetric too). Formula used division that can be done in general case only by prime modulo.

But it can be solved without knowing any special about these polynomials. In this case solution doesn't need the primality of P. And then we have a data structure problem only, not number theoretical :)  I used interval tree and memoization of sums on subsegments. And still the 4 seconds limitation is too large.

upd: Fenwick tree is better ;)

Edited by author 10.09.2011 23:40

I understand how to solve the problem with combinatoric formula and 4 segment trees, can you please explain the second way?