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.
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 Cantor-Zassenhaus algorithm (a beautiful randomized algorithm backed by cool theories). For implementation details, you can check my code with comments here.
Subtask 4: Now, the idea is similar to the one used in “SHAIKHGN”, the problem in August challenge. Here precompute the {2}^{i} powers of the matrix used for recurrence. For the final answer, we just need one row of the matrix, not the full matrix. Just this can be done in O({n}^{2} \log{x}) per query which passes is this subtask but is too slow for even subtask 2 and 5 because there is a pre-computation cost of O(64 * {n}^{3}) which is too slow. This can be reduced by half, by using the fact the {a}^{phi(m)} \equiv 1 (\bmod {m}), thus we need only powers will {2}^{30}
Subtask 5 / Full Solution: Use the method of generating functions. For this, I recommend you all to go through his awesome editorial on problem RNG by Kevinsogo for solving recurrences in general in O({n}^{2} \log {x}) complexity naively. Here FFT part described in editorial is not required and also not possible as 1000000007 = 2*5000000003 + 1 i.e. k = 1 as per FFT equation. So, just naive calculation of value of points and polynomial multiplication solves the problem.
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.
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.
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}).
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!
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.
@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.”
@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.
@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).
@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.
Fermat theorem holds only when gcd(a,p)=1
The theorem a^(p-1)=1 mod§ 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 §. 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^(p-1) = 1 mod§ 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.”
@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.
