Problem link: https://uva.onlinejudge.org/external/121/p12143.pdf

I got a solution here : http://mypaper.pchome.com.tw/zerojudge/post/1325083499

But I failed to understand how the problem is reduced to gaussian elimination. Can anybody explain please? If there are any other ideas please feel free to share.

Thanks for you help.

Here's my understanding of the solution provided in your link:

A sufficiently 'nice' sum that depends only on N will be a polynomial on N. I don't have a definition of 'nice' or a proof that this sum is 'nice', but several examples should convince you of this — or or .

Furthermore, the degree of the polynomial should be 10. We're multiplying five terms and summing over five variables. Again, take a look at the above examples — the third one should be a degree-three polynomial in N, as we are multiplying one term and summing over two variables.

Unfortunately, we don't know the coefficients of this magical 10th degree polynomial. However, we can find them if we have 10 linear equations in terms of these coefficients. Let

P(N) =c_{10}x^{10}+ ... +c_{1}x+c_{0}. Then our desired equations areP(N_{i}) =c_{10}(N_{i})^{10}+ ... +c_{1}N_{i}+c_{0}for 10 differentN_{i}, whereP(N_{i}) must be calculated manually or with a slow program.Finally, we put these equations into an augmented matrix and use Gaussian elimination to solve for the 'variables', which are the 10 coefficients

c_{i}. Now we simply evaluateP(N) for each givenN.Thanks for your explanation. It seems helpful :)