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.