Since the editorial is taking too long I would like to know if anyone could explain the solution for the large test case of powsums. For the first test cases I used matrix exponentiation based on the recurrence relations of Newton's identities. This solution worked on O(n^2) per query but required expensive pre calculation of O(n^3) (x30) step per test case and of course this would be too large to pass the larger test cases. I even thought of using a faster multiplication algorithm but it seemed more like an optimization and not really the intended solution. I thought of 2 other approaches: 1  Computing the eigen decomposition so I could reduce the time complexity from cubic to quadratic. 2  Finding the roots of the polynomials so on each query I could compute the sums of powers directly. But I failed, the articles on eigendecomposition are still hard to digest for me and had no success of finding/calculating the roots of the polynomials. The best I could do was to use Fermat's little theorem to reduce the range of xi from 10e18 to 10e9. asked 17 Oct '16, 23:27
showing 5 of 10
show all

This was my favourite question in the whole contest with each subtask teaching something new. Let me go in systematic manner:
Thus the conclusion from now on, whenever you see recurrence and want to solve it, use the method of generating functions, instead of matrix multiplications. Also if you see a new type of prime, and is of the for ${2}^{k}.{m} + 1$ then, it is a hint that FFT is also required for the problem. That is all from my side. If you have any doubts, ask in the comments section below. Happy coding :) answered 18 Oct '16, 00:08
If you feel, you question was answered, mark it as accepted.
(18 Oct '16, 00:09)
Actually, the solution you said for subtask 4 works for 100 points. You just need to reduce the number of modulo operations you do drastically :)
(18 Oct '16, 00:46)
@animesh_f, I thought the same thinking but couldn't make if fast enough. I managed to make the multiplication faster but still doing 30 multiplications on a 300*300 matrix was too expensive.
(18 Oct '16, 17:23)
2
@likecs, I'm going to mark your answer as accepted because it's more detailed and the solution is very close to what I had in mind (I did something similar to your approach on Subtask 4).
(18 Oct '16, 17:25)
FFT part described in editorial is not required and also "not possible". It is hard to do that here but it is possible!
(19 Oct '16, 17:21)

The first subtask can be done by simple algebraic manipulations, I handled it separately. Notice that Newton's sums give you a set of equations, which you can use to recover the coefficients $c_i$ of an $n$degree polynomial with leading coefficient $c_n=1$, whose roots are the hidden $a_i$ values in the problem. So you only need to solve this polynomial in $\mathbb{Z}/p~$ i.e. modulo $p=10^9+7$ and answer the queries by brute force + binary exponentiation. I solved the polynomial using CantorZassenhaus algorithm (a beautiful randomized algorithm backed by cool theories). For implementation details, you can check my code with comments here. answered 17 Oct '16, 23:51
Mathamazing!
(17 Oct '16, 23:52)
@nirjhor, thank you. You should probably your full solution. I see it's different from most (including mine), who tried/solved the full problem without finding the roots of the polynomials. I voted @likecs answer because at the time I find it easier to understand.
(18 Oct '16, 17:31)
@junior94: I didn't find any further detail to add as I found my solution very straightforward. However if you have any query about this approach, do let me know.
(18 Oct '16, 18:21)

Wow I never knew that we could solve it with faster methods. I used matrix exponentiation and the trick is to have an efficient matrix multiplication and to precompute $M, M^{2}, ..., M^{2^{60}}$. This can be done in $O(n^{3}\log 10^{18})$. Now, each query can be answered by multiplying some set of matrices with a suitable vector (which is what you'd do normally), and the trick is to multiply the matrices with the vector instead of with other matrices. This way, each query can be answered in $O(n^2\log 10^{18})$. answered 18 Oct '16, 03:37
Nice solution zscoder. Can you explain how to do this part " trick is to multiply the matrices with the vector instead of with other matrices."? Thanks!
(18 Oct '16, 05:42)
2
The method zscoder is using is the same as I described in my approach of Subtask 4. The only difference is the mod operations. As stated by @animesh_f also, many people have optimised their code heavily with respect to MOD operations.
(18 Oct '16, 09:20)

Eigen decomposition is O(N^3) for general matrices i think. Can you explain how to use Fermat's little theorem to reduce the range?
Yes, each power sum is equal to a1^k + a2^k + ... + an^k for some k. On the input they give us the powers sums for 1 <= k <= n. Now take a random element, let's say a1. In the first power sum this element will be a1, in the second it will be a1^2 and so on...
According to fermat's little theorem when k = 1e9+7, this element will be equal to a1^1 again. Therefore a1 = a1^1e9+7 and a1^2 = a2^1e9+8 and so on (this is a cycle where we can apply the modulo operation since saying k=1e9+7 is the same as saying k=1, k=1e9+8 is the same as k=2 and so on...)
@ junior94 : Fermat little theorem will not work here because a_i is non negative so a_i can be 0.According to fermat theorem gcd(a_i,mod)=1, which is not true in case when a_i=0. You can see it easily so your assumption to reduce it by a factor of 2 is wrong.
@divakar_tomar, when a_i is 0 we can just decrease the value of n until it is equal to the number of positive values in the power sum. Taking advantage of Newton's identities (see the wikipedia page) we could just look for the largest positive e[n].
When I applied the modulo on X, I didn't have to use this trick but was thinking about resorting to it if needed. And even without the trick it was working correctly for the example test case (in which one of the elements was equal to zero).
That said, if you case, please provide a test case that fails using FLT.
Still, could you point to an article that explains the requirement for the gcd to be 1. The ones I found so far state that it works for any integer. Quoting from the wikipedia page:
"Fermat's little theorem states that if p is a prime number, then for any integer a, the number a p − a is an integer multiple of p."
Fermat theorem holds only when gcd(a,p)=1 The theorem a^(p1)=1 mod(p) fails if a is 0. You can substitute a=0 and check. But a^p=a (mod p) holds. Coming to question, I am still not clear if we can use Fermat's Theorem here?
In this case I'm using the part that states that a^p = a mod (p). Wouldn't this be correct then? Since p is a prime number and 0 to the power of this prime would still be 0.
According to Wikipedia, the part a^(p1) = 1 mod(p) is a special case when a is not divisible by p.
Perhaps you're thinking about the case that applies to modulo inverse (the second one). Here I'm using the part of the theorem that holds for any integer a.
Quoting again:
"Fermat's little theorem states that if p is a prime number, then for any integer a, the number a^p − a is an integer multiple of p."
Ok, so how do use Fermat's theorem? Like if an xi comes, what do you do? Take xi mod (p1) or what?
@divakar_tomar: The assertion $a^p\equiv a\pmod p~$ is true for any integer $a$ and prime $p$. The requirement $\gcd(a,p)=1~$ is only needed for the assertion $a^{p1}\equiv 1\pmod p~$ because you divide both sides by $a$ then. When $\gcd(a,p)\neq 1~$ that is, $p$ divides $a$, then $a^p$ is divisible by $p$ as well so we can still apply the reduction stated by @junior94 here.
So we take xi mod p or xi mod (p1) to make reduction?