407708: GYM102878 J Teacher Long and Machine Learning

Teacher Long is currently studying machine learning. Today, he focuses on a question about regression.

'Suppose a polynomial F satisfies F(1)=1, F(2)=4, F(3)=9, F(4)=16, F(5)=25, then F should be:'

$$$F(x) = x^2$$$ (Correct)

'Suppose a polynomial F satisfies F(1)=1, F(2)=4, F(3)=9, F(4)=16, F(5)=24, then F should be:'

$$$F(x) = -\frac{1}{24}x^4+\frac{5}{12}x^3-\frac{11}{24}x^2+\frac{25}{12}x-1$$$ (Wrong)

Correct answer :

$$$F(x) = x^2$$$ , since there is noise of value 1 in $$$F(5)$$$.

Teacher Long felt so bad, and decided to write a code to help him automatically calculate this kind of problem.

Suppose there is a fourth-order polynomial $$$F(x)=a_4x^4+a_3x^3+a_2x^2+a_1x+a_0$$$ and a given sequence $$$\{f_1,f_2,f_3,f_4,f_5\}$$$, satisfying that the coefficients are all in range $$$[-100, 100]$$$ and are all integers, and for $$$\forall i\in[1,5],|F(i)-f_i|\le1$$$ . Given $$$\{f_1,f_2,f_3,f_4,f_5\}$$$, calculate $$$\{a_0,a_1,a_2,a_3,a_4\}$$$.

There are multiple test cases in input data.

An integer $$$T$$$ is in the first line, standing for the total number of test cases.

Next is $$$T$$$ test cases.

For each test case, the input data is one line with five numbers, with $$$f_1,f_2,f_3,f_4,f_5$$$ respectively.

Print $$$T$$$ lines. Each line is the answer of one test case, with $$$a_0,a_1,a_2,a_3,a_4$$$ respectively.

3
1 4 9 16 25
1 4 9 16 24
25 16 9 4 1

0 0 1 0 0
0 0 1 0 0
36 -12 1 0 0

For $$$100\%$$$ data, it's guaranteed that $$$1\le T\le 10$$$. There is at least one valid answer.